二叉树中的奇偶树问题

目录

一·题目：

二·思路汇总：

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;}
};