题目

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

• 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
• 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
• 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

通俗的说，就是一颗二叉树，从0开始作为层数，偶数层节点值从左往右为奇数递增，奇数层节点为从左往右偶数递减。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/even-odd-tree

解答

需要一层一层的遍历，自然想到二叉树的层序遍历。

通过队列结构，存储每一行的节点，依次出队进行遍历即可。

class Solution {
public:
    bool isEvenOddTree(TreeNode *root) {
        queue<TreeNode *> qu;
        int floor = 0; // 保存当前层数

        // 根节点入队
        qu.push(root);

        while (!qu.empty()) {
            int num = (int) qu.size();
            auto first = qu.front();
            qu.pop();

            if ((floor % 2 == 0 && first->val % 2 == 0) ||
                (floor % 2 == 1 && first->val % 2 == 1)) {
                return false;
            }

            if (first->left) {
                qu.push(first->left);
            }
            if (first->right) {
                qu.push(first->right);
            }

            int last = first->val;

            for (int i = 1; i < num; ++i) {
                auto cur = qu.front();
                qu.pop();

                if (floor % 2 == 0) {
                    // 偶数层，应该为递增奇数
                    if (cur->val <= last || cur->val % 2 == 0) {
                        return false;
                    }
                } else {
                    // 奇数层，应该为递减偶数
                    if (cur->val >= last || cur->val % 2 == 1) {
                        return false;
                    }
                }
                last = cur->val;

                if (cur->left) {
                    qu.push(cur->left);
                }
                if (cur->right) {
                    qu.push(cur->right);
                }
            }
            floor++;
        }

        return true;
    }
};