Day127 | 灵神 | 二叉树 | 奇偶树

1609.奇偶树

1609. 奇偶树 - 力扣（LeetCode）

思路：

这道题用层序遍历的思路比较好想，就是往for循环里面加一个if，如果是奇数层就判断是不是偶数并且递减，如果是偶数层就判断是不是奇数并且递增，会很直接的写下如下所示的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode *> q;
        int count=0;
        if(root==nullptr)
            return true;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                q.pop();
                //偶数层 全奇递增
                if(count%2==0)
                {
                    if(t->val%2!=1)
                        return false;
                    if(!q.empty()&&t->val>=q.front()->val)
                        return false;
                }
                else
                {
                    if(t->val%2!=0)
                        return false;
                    if(!q.empty()&&t->val<=q.front()->val)
                        return false;
                }
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            count++;
        }
        return true;
    }
};

但是很显然这个是有问题的，因为我这里是用当前结点和队头元素进行比较，那我当前这一层的节点就有可能和下一层的节点进行比较，这是明显的错误，因为下一层的奇数或者偶数和本层的奇数或者偶数没有关系，所以导致了错误。

所以不可以用当前结点和队头元素进行比较，而是需要一个新的变量pre来记录前驱节点，方便进行比较，并且每一层开始前都把pre初始化为最大值或者最小值

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        
        while (!q.empty()) {
            int size = q.size();
            int prev = (level % 2 == 0) ? INT_MIN : INT_MAX;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 检查奇偶性
                if (level % 2 == 0) {
                    if (node->val % 2 != 1 || node->val <= prev) return false;
                } else {
                    if (node->val % 2 != 0 || node->val >= prev) return false;
                }
                prev = node->val;
                
                // 添加子节点
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            level++;
        }
        return true;
    }
};