[数据结构与算法]LeetCode 1609 奇偶树(BFS)

1609. 奇偶树https://leetcode-cn.com/problems/even-odd-tree/

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

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

?简单BFS，看清题目的要求就可以，条件比较多，注意别漏了

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Deque<TreeNode>queue=new LinkedList<>();
        TreeNode node=root;
        queue.offer(node);
        int depth=0;
        //深度用来确定奇偶性
        //BFS
        while(!queue.isEmpty()){
            //奇偶性
            int target=depth%2==0?1:0;
            //相当于在最左边值的左边再加一个值，根据奇偶性赋初始值
            int num=target==0?1000001:0;
            int size=queue.size();
            for(int i=0;i<size;i++){
                //更新队列
                node=queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                //验证奇偶性
                if(node.val%2!=target){
                    return false;
                }
                //验证增减性
                if(target==1&&node.val<=num){//偶数层
                    return false;
                }else if(target==0&&node.val>=num){//奇数层
                    return false;
                }
                num=node.val;
            }
            depth++;
        }
        return true;
    }
}