题目

类型：二叉树、深度优先搜索

解题思路

使用广度优先搜索，每一轮搜索访问同一层的全部节点，且只会访问这一层的节点。

使用队列存储节点。初始时，将根节点加入队列。每一轮搜索之前，队列中的节点是同一层的全部节点，记队列的大小为 size，该轮搜索只访问 size 个节点，即可保证该轮搜索访问的恰好是同一层的全部节点。搜索过程中，将当前层的节点的非空子节点依次加入队列，用于下一层的搜索。

判断一棵二叉树是否为奇偶树，需要考虑两个条件，一是节点值的奇偶性，二是节点值的单调性，这两个条件都由层下标的奇偶性决定。因此，需要维护搜索到的层下标，以及对于每一层搜索都需要维护上一个节点值。

如果当前层下标是偶数，则要求当前层的所有节点的值都是奇数，且节点值从左到右严格递增。如果遇到节点值是偶数，或者当前节点值小于等于上一个节点值，则二叉树一定不是奇偶树。
如果当前层下标是奇数，则要求当前层的所有节点的值都是偶数，且节点值从左到右严格递减。如果遇到节点值是奇数，或者当前节点值大于等于上一个节点值，则二叉树一定不是奇偶树。
如果二叉树的所有节点都满足奇偶树的条件，则二叉树是奇偶树。

代码

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            int prev = level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int value = node.val;
                if (level % 2 == value % 2) {
                    return false;
                }
                if ((level % 2 == 0 && value <= prev) || (level % 2 == 1 && value >= prev)) {
                    return false;
                }
                prev = value;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            level++;
        }
        return true;
    }
}