1609.奇偶树

链接：1609.奇偶树
难度：Medium
标签：树、广度优先搜索、二叉树
简介：给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

题解 1 - cpp

• 编辑时间：2021-12-25
• 执行用时：216ms
• 内存消耗：147.2MB
• 编程语言：cpp
• 解法介绍：层序遍历。

class Solution {
   public:
    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int size = 1, data = 1, pre = 0;
        while (q.size()) {
            TreeNode* node = q.front();
            if ((node->val & 1) != data) return 0;
            if (data == 1 && node->val <= pre || data == 0 && node->val >= pre)
                return 0;
            q.pop();
            pre = node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            if (--size == 0) {
                size = q.size();
                data ^= 1;
                pre = data ? 0 : 1e6;
            }
        }
        return 1;
    }
};