lc1609. 奇偶树（层序遍历）

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

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

示例 1：

输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。
示例 2：

输入：root = [5,4,2,3,3,7]
输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
示例 3：

输入：root = [5,9,1,3,5,7]
输出：false
解释：1 层上的节点值应为偶数。
示例 4：

输入：root = [1]
输出：true
示例 5：

输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出：true

提示：

树中节点数在范围 [1, 105] 内
1 <= Node.val <= 106

class Solution {
    /**
    本题采用层序遍历解决，将每层的节点放入队列，对于每一层分为偶数层和奇数层
    进行判断，偶数层必须都是奇数且单调递增，奇数层必须都是偶数且单调递减
     */
    public boolean isEvenOddTree(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = -1;
        while (!queue.isEmpty()) {
            count++;
            int size = queue.size();
            int prev = 0;
            while (size -- > 0) {
                TreeNode node = queue.poll();
                //当做当前值的上一个值，用来判断与当前值的大小关系
                int cur = node.val;
                //偶数层时
                if ((count & 1) == 0) {
                    //如果为偶整数或者不是严格单调递增直接返回false
                    if ((node.val & 1) == 0) return false;
                    if (prev != 0 && cur <= prev) return false;
                }
                //技术层时 
                else {
                    //如果为奇整数或者不是严格单调递减直接返回false
                    if ((node.val & 1) == 1) return false;
                    if (prev != 0 && cur >= prev) return false;
                }
                prev = cur;
                //将左右子节点放入队列
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return true;
    }
}