二叉树中的奇偶树问题

目录

一·题目：

二·思路汇总：

1.二叉树层序遍历：

1.1题目介绍：

1.2 解答代码（c版）：

1.3 解答代码（c++版）：

1.4 小结一下：

2.奇偶树分析：

2.1 被leetcode强制否定的思路：

2.2被迫转换的思路：

三·解答代码：

一·题目：

leetcode链接： 1609. 奇偶树 - 力扣（LeetCode）

二·思路汇总：

1.二叉树层序遍历：

1.1题目介绍：

解答这道题，其实首先可以说是和leetcode上的另一道题相关，即二叉树的层序遍历：

leetcode链接：. - 力扣（LeetCode） 

对这道题也就不过多解释了，只是用到了这道题的相关代码，可以说是奇偶树是基于这道题。

1.2 解答代码（c版）：

//思路：利用队列先进先出，后进后出原则，把树的节点放入，每次取出队列第一个元素，就把它的val按照顺序放入数组
//然后保存并pop掉，放入左右孩子节点（不为NULL），由于是放入二维数组的每一行，故利用for循环，每次计算队列数据个数来控制
//最后注意每次放入二维数组每一行后既for完成一次换行。//接口函数要完成的任务：1·返回层序遍历树得到的按规定的二维数组指针.2·改变并得到二维数组的总行数。3·改变对应的每行的列数typedef  struct TreeNode *qdatatype;
typedef struct Qnode {struct Qnode* next;qdatatype data;
}Qnode;
typedef struct queue {int size;Qnode* head;Qnode* tail;
}queue;
void Queueinit(queue* p) {assert(p);p->head = p->tail = NULL;p->size = 0;
}void Queuedestroy(queue* p) {assert(p);Qnode* cur = p->head;while (cur) {Qnode* next = cur->next;free(cur);cur = next;}p->size = 0;p->tail = p->head = NULL;
}
void Queuebackpush(queue* p, qdatatype x) {assert(p);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));if (newnode == NULL) {perror(malloc);return;}newnode->next = NULL;newnode->data = x;if (p->tail == NULL) {p->head = p->tail = newnode;}else {p->tail->next = newnode;p->tail = newnode;}p->size++;}
qdatatype Queuefrontdata(queue* p) {assert(p);assert(p->size > 0);return p->head->data;
}
bool QueueEmpty(queue* p) {assert(p);return p->size == 0;
}
void Queuefrontpop(queue* p) {assert(p);assert(p->size > 0);if (p->head->next == NULL) {free(p->head);p->head = p->tail = NULL;}else {Qnode* next = p->head->next;free(p->head);p->head = next;}p->size--;
}
int Queuesize(queue* p) {assert(p);return p->size;
}
//以上是开辟的队列int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {* returnSize=0;int**pp=(int**)calloc(2000,sizeof(int*));//利用二级指针来开辟二维数组，首先开辟2000行，可以理解为下面再利用每一行的首地址来开辟每一行的一维数组，即列数if(root==NULL){return NULL;}//空树直接返回NULLqueue q;Queueinit(&q);Queuebackpush(&q, root);//先放入树的根节点int row=0;//树的层数int count=0;//每层树的节点的个数*returnColumnSizes = (int*)malloc(sizeof(int) * 2000);//在外部传的是&arr通过函数来改变数组内的数据，故用二级指针接受//为每行开辟2000个空间while (!QueueEmpty(&q)) {count= Queuesize(&q);//当pop掉上一行所有节点，重新计算队列数据个数即下面要放入数组的每行的数据个数(*returnColumnSizes)[row]=count;//记录每行列数pp[row]=(int*)calloc(count,sizeof(int));//放入数组：得到每行的首地址，在此开辟一维数组，即二维数组每行的列数for(int i=0;i<count;i++){struct TreeNode*ret=Queuefrontdata(&q);pp[row][i]=ret->val;Queuefrontpop(&q);if (ret->left!= NULL) {Queuebackpush(&q, ret->left);}if (ret->right!= NULL) {Queuebackpush(&q, ret->right);}}//利用for循环将上一层节点所连的左右子节点放入，满足队列内数据个数就是下一层的行的列数row++;}Queuedestroy(&q);*returnSize=row;return pp;}

1.3 解答代码（c++版）：
 

//思路：把树的节点入队列，每次队列数据入v后pop调，之后拉进它的左右孩子入队，队列的大小就是二维数组每行的数据数，依次两个循环嵌套。
class Solution{
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<int>v;vector<vector <int>>vv;queue<TreeNode*> q;if(root==NULL){return vv;}q.push(root);while(!q.empty()){int size=q.size();int count=size;//记录每行大小也是push——back次数v.clear();//刷新v里面的数据while(count--){//vv[row].push_back(q.front()->val);因为一开始定义的vv没有开辟空间，故不能这样用下标访问，只有下面的push_back才//开了空间，故可以直接插入数据。类似于用malloc给指针开辟空间，再用下标访问，而这里相当于用malloc故访问越界v.push_back(q.front()->val);TreeNode*tmp=q.front();//保存节点指针方便后面pushq.pop();if(tmp->left!=NULL){q.push(tmp->left);}if(tmp->right!=NULL){q.push(tmp->right);}}vv.push_back(v);//每push完一层就加到vector后面。}return vv;}
};

1.4 小结一下：

根据对于同一道题的解答代码长度和复杂度上，明显c++直接占极大优势，感觉当初花很长时间的c代码直接让c++代码瞬间秒杀，而且难度也减小，不亏是c的升级版，感觉爱不释手了。

2.奇偶树分析：

2.1 被leetcode强制否定的思路：

先说一下一开始吧，本以为，如果先把它按照层序遍历到二维数组的话，后面再对已知条件进行一次判断的话，本来以为可以通过（当看到测试用例过了）：

然而当提交的时候，果然还是被leetcode给算计住了（其实当看到val精确到10^6就觉得可能会来这一套，说实话也没太出乎意料吧）：

 

这里用了简单hash表以及is_sorted() 等最后来判断是否符合，不过这下子只能换思路咯！

错误代码（仅参考一下这个思路吧，不过也pass掉咯）：

class Solution {
public:bool isEvenOddTree(TreeNode* root) {vector<int>v;vector<vector <int>>vv;queue<TreeNode*> q;if (root == NULL) {return false;}q.push(root);while (!q.empty()) {int size = q.size();int count = size;//记录每行大小也是push——back次数v.clear();//刷新v里面的数据while (count--) {//vv[row].push_back(q.front()->val);因为一开始定义的vv没有开辟空间，故不能这样用下标访问，只有下面的push_back才//开了空间，故可以直接插入数据。类似于用malloc给指针开辟空间，再用下标访问，而这里相当于用malloc故访问越界   v.push_back(q.front()->val);TreeNode* tmp = q.front();//保存节点指针方便后面pushq.pop();if (tmp->left != NULL) {q.push(tmp->left);}if (tmp->right != NULL) {q.push(tmp->right);}}vv.push_back(v);//每push完一层就加到vector后面。}if(vv[0][0]%2==0){return false;}for(int i=0;i<vv.size();i++){int hash[1000001]={0};for(int j=0;j<vv[i].size();j++){if(i%2==0&&vv[i][j]%2==0){return false;}if(i%2!=0&&vv[i][j]%2!=0){return false;}if(hash[vv[i][j]]>=1){return false;}hash[vv[i][j]]++;}if(i%2==0){if(is_sorted(vv[i].begin(),vv[i].end(),less<int>())){}else{return false;}}else{if(is_sorted(vv[i].begin(),vv[i].end(),greater<int>())){}else{return false;}}}return true;}
};

 

2.2被迫转换的思路：

下面于是就想着可以在放入内部嵌套的vector 的过程中来判断是否符合。

由于把它依靠队列放入vector模拟的二维数组再判断奇偶层对应的奇偶数已经严格递增的话可能超过了时间限制，故可以换个思路，考虑当由队列放入v中就按照顺序筛选，（由于只要出现一种不符合条件的情况，它就不是奇偶数，故找到不合题意就直接给它false，剩下的直接最后true就OK）

筛选条件：level要么是奇数要么是偶数，为奇的话，插入的数据应该是偶，为偶的话，插入的数据应该是奇，否则直接false。 偶奇：如果是第一个先直接插入，但是也要有个比较v中的数据要小于要插入的才插入，否则也直接false。

 同理 奇偶也是如此：如果是第一个先直接插入，但是也要有个比较v中的数据要大要插入的才插入，否则也直接false。

   

    步骤总结：

   1.先模拟二叉树进入vector模拟的二维数组过程

    2.进入vector的时候加上筛选条件

最后也是成功被leetcode放行通过了：

尽管这种方法效率有点低吧！！！

三·解答代码：

class Solution {
public:bool isEvenOddTree(TreeNode* root) {vector<int>v;vector<vector <int>>vv;queue<TreeNode*> q;if (root == NULL) {return false;}q.push(root);int row = -1;while (!q.empty()) {int size = q.size();row++;//记录level的值int count = size;//记录每行大小也是push——back次数v.clear();//刷新v里面的数据while (count--) {//vv[row].push_back(q.front()->val);因为一开始定义的vv没有开辟空间，故不能这样用下标访问，只有下面的push_back才//开了空间，故可以直接插入数据。类似于用malloc给指针开辟空间，再用下标访问，而这里相当于用malloc故访问越界   if (row % 2 == 0 && q.front()->val % 2 != 0) {//判断为偶奇if (v.size() == 0) {v.push_back(q.front()->val);}else if (v.end() == find(v.begin(), v.end(), q.front()->val) && v[v.size() - 1] < q.front()->val){v.push_back(q.front()->val);//判断严格升序}else {return false;//非严格升序}}else if (row % 2 != 0 && q.front()->val % 2 == 0) {//判断为奇偶if (v.size() == 0) {v.push_back(q.front()->val);}
else  if (v.end() == find(v.begin(), v.end(), q.front()->val) && v[v.size() - 1]> q.front()->val){v.push_back(q.front()->val);//判断严格降序}else {return false;//非严格降序}}else {//非->直接返falsereturn false;}TreeNode* tmp = q.front();//保存节点指针方便后面pushq.pop();if (tmp->left != nullptr) {q.push(tmp->left);}if (tmp->right != nullptr) {q.push(tmp->right);}}vv.push_back(v);//每push完一层就加到vector后面。}return true;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/405791.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

glibc 2.24 下 IO_FILE 的利用

glibc 2.24 下 IO_FILE 的利用

文章目录 glibc 2.24 下 IO_FILE 的利用介绍&#xff1a;新的利用技术fileno 与缓冲区的相关利用实例&#xff1a;1. _IO_str_jumps -> overflow实例&#xff1a; 2. _IO_str_jumps -> finish实例: 最后拓展一下上一篇博客house of orange题目的做法: glibc 2.24 下 IO_F…
阅读更多...
Oracle基本SQL操作-用户角色权限管理

Oracle基本SQL操作-用户角色权限管理

一、用户权限管理 -- 创建锁定用户&#xff0c;此时用户不可用 create USER zhucl IDENTIFIED BY 123456 account lock; 会提示用户被锁定&#xff1a; -- 删除用户 drop user zhucl;-- 重新创建用户&#xff0c;不锁定 create user zhucl IDENTIFIED BY 123456 account unlo…
阅读更多...
嵌入式和单片机有什么区别？

嵌入式和单片机有什么区别？

目录 &#xff08;1&#xff09;什么是嵌入式&#xff1f; &#xff08;2&#xff09;什么是单片机&#xff1f; &#xff08;3&#xff09;嵌入式和单片机的共同点 &#xff08;4&#xff09;嵌入式和单片机的区别 &#xff08;1&#xff09;什么是嵌入式&#xff1f; 关…
阅读更多...
45.x86游戏实战-XXX封包组包拼包详解

45.x86游戏实战-XXX封包组包拼包详解

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 工具下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1rEEJnt85npn7N38Ai0_F2Q?pwd6tw3 提…
阅读更多...
提车后遇大降价被指“背刺”车主，方程豹的口碑问题何解？

提车后遇大降价被指“背刺”车主，方程豹的口碑问题何解？

进入8月下旬&#xff0c;汽车市场“金九银十”的销售旺季即将到来&#xff0c;将行业“内卷”推向新高峰。即便有宝马等高端豪华品牌退出“价格战”的先例&#xff0c;但为刺激销量&#xff0c;不少车企依旧推出了各式各样的价格优惠政策&#xff0c;行业内部价格竞争狼烟四起。…
阅读更多...
Kotlin 流flow、ShareFlow、StateFlow、Channel的解释与使用

Kotlin 流flow、ShareFlow、StateFlow、Channel的解释与使用

一、介绍 随着Android接入kotlin开发&#xff0c;Android之前好多模式也渐渐被kotlin替代。开发模式也在做渐进的转型&#xff0c;从MVC到MVP在到MVVP以及现在的MVI等。 流IO在java中和kotlin中使用率都是比较高的&#xff0c;场景很多。如Java的IO和NIO&#xff0c;再到我们现…
阅读更多...
Java、python、php版的高校失物招领平台（源码、调试、LW、开题、PPT）

Java、python、php版的高校失物招领平台（源码、调试、LW、开题、PPT）

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人 八年开发经验&#xff0c;擅长Java、Python、PHP、.NET、Node.js、Android、微信小程序、爬虫、大数据、机器学习等&#xff0c;大家有这一块的问题可以一起交流&…
阅读更多...
kali网络代理设置

kali网络代理设置

首先主机必须有自己的代理。记住主机的ip和代理端口。 在kali中打开终端&#xff1a; vim /etc/proxychains4.conf输入代理进行更改 把这行注释掉&#xff0c;在下一行输入 socks5 主机ip 代理端口 点击esc&#xff0c;在:wq退出保存。 配置完成。
阅读更多...
Salesforce 发布开源大模型 xGen-MM

Salesforce 发布开源大模型 xGen-MM

xGen-MM 论文 在当今 AI 技术飞速发展的时代&#xff0c;一个新的多模态 AI 模型悄然崛起&#xff0c;引起了业界的广泛关注。这个由 Salesforce 推出的开源模型—— xGen-MM&#xff0c;正以其惊人的全能特性和独特优势&#xff0c;在 AI 领域掀起一阵旋风。那么&#xff0c;x…
阅读更多...
Why Does ChatGPT Fall Short in Providing Truthful Answers?

Why Does ChatGPT Fall Short in Providing Truthful Answers?

文章目录 题目摘要简介相关工作模型和数据集结果事实性背后的能力提高 QA 的事实性结论 题目 为什么 ChatGPT 无法提供真实的答案&#xff1f; 论文地址:https://arxiv.org/abs/2304.10513 摘要 ChatGPT 等大型语言模型的最新进展已显示出影响人类生活各个方面的巨大潜力。然而…
阅读更多...
数据库学习（进阶）

数据库学习（进阶）

数据库学习&#xff08;进阶&#xff09; Mysql结构:连接层&#xff1a;服务层&#xff08;核心层&#xff09;&#xff1a;存储引擎层&#xff1a;系统文件层&#xff1a; 存储引擎&#xff08;概述&#xff09;:存储引擎特点&#xff1a;InnoDB存储引擎&#xff1a;(为并发条…
阅读更多...
【C++ 面试 - 面向对象】每日 3 题（二）

【C++ 面试 - 面向对象】每日 3 题（二）

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…
阅读更多...
C语言钥匙迷宫2.0

C语言钥匙迷宫2.0

目录 开头程序程序的流程图程序游玩的效果结尾 开头 大家好&#xff0c;我叫这是我58。废话不多说&#xff0c;咱们直接开始。 程序 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <string.h> #include <Windows.h> enum color {Y,B,R …
阅读更多...
裸金属服务器和裸金属云服务器：区别、优势与选择

裸金属服务器和裸金属云服务器：区别、优势与选择

首先&#xff0c;必须肯定的是&#xff1a;裸金属服务器和裸金属云服务器是有区别的。 ‌ 二者的概述 裸金属服务器&#xff08;‌Bare Metal Server&#xff09;‌是一种物理服务器&#xff0c;‌它直接在硬件上运行&#xff0c;‌没有额外的虚拟化层。‌这意味着每个应用程…
阅读更多...
ChatGLM-4-9b-chat本地化｜天翼云GPU上vLLM本地部署开源模型完整攻略

ChatGLM-4-9b-chat本地化｜天翼云GPU上vLLM本地部署开源模型完整攻略

“ 拥有一个私有化的领先国产开源大模型&#xff1f;本文详细介绍了如何在天翼云GPU上使用vLLM部署ChatGLM-4-9b-chat本地化模型的完整攻略&#xff0c;助您快速上手。” 01 — vLLM 本来打算用ollama在GPU服务器上部署开源模型GLM4&#xff0c;在之前文章有部署教程&#xff1…
阅读更多...
刷题篇 - 03

刷题篇 - 03

题目一&#xff1a; 203. 移除链表元素 - 力扣&#xff08;LeetCode&#xff09; public ListNode removeElements(ListNode head, int val) {//1. 如果链表为null&#xff0c;直接返回headif (head null) {return head;}//2. 定义快慢指针ListNode pre head;ListNode del …
阅读更多...
Tomcat：Web 领域的闪耀明珠，魅力何在？

Tomcat：Web 领域的闪耀明珠，魅力何在？

一、Web技术 HTTP 协议&#xff08;HyperText Transfer Protocol&#xff0c;超文本传输协议&#xff09;是互联网上应用最为广泛的一种网络协议。它的主要作用是在客户端和服务器之间传输超文本数据&#xff0c;如网页、图片、视频等。 HTTP 协议的特点 无状态性 HTTP 协议是…
阅读更多...
STM32H7双路CAN踩坑记录

STM32H7双路CAN踩坑记录

STM32H7双路CAN踩坑记录 目录 STM32H7双路CAN踩坑记录1 问题描述2 原因分析3 解决办法4 CAN配置参考代码 1 问题描述 STM32的CAN1和CAN2无法同时使用。 注&#xff1a;MCU使用的是STM32H743&#xff0c;其他型号不确定是否一样&#xff0c;本文只以STM32H743举例说明。 2 原因…
阅读更多...
mysql io_setup() failed with EAGAIN. Will make 5 attempts before giving up.

mysql io_setup() failed with EAGAIN. Will make 5 attempts before giving up.

报错 解决方案 sysctl -w fs.aio-max-nr1048576
阅读更多...
了解同步带选择同步带

了解同步带选择同步带

同步带和轮选型 同步带传动属于皮带传动&#xff0c;但是改进了传统皮带传动无法保持严格的传动比的打滑问题&#xff0c;传统皮带传动依靠皮带和皮带轮张紧时产生的摩擦力传输动力&#xff0c;但是从动轮遇到障碍或超载荷时&#xff0c;皮带会在皮带轮产生滑动。 解决打滑问题…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023