[数据结构与算法]LeetCode——1609.奇偶树

大佬，牛！！！

• 题目：给定一颗二叉树，其中层数从0开始，然后如果满足两个条件，就称为奇偶树，则返回true
  • 奇数层，所有节点必须是偶数，并且严格递减；
  • 偶数层，所有节点必须是奇数，并且严格递增。
• 思路：
  • 我的思路：首先，这就是二叉树的层序遍历，可以用队列的。然后就是判断这是那一层，以及节点的判断。但是光判断那一层，我就想了好久，思路一直不稳定，写的代码也是乱糟糟的。其次，就是判断递减这一块。并且里面还穿插着null，一时不知道如何下手。
  • 大佬的思路总结：我们可以这样，每次再队列中处理一层，直到队列为空。那么如何处理一层，就是比较关键的问题。
    • 我们每次开始处理的时候，这一层应该都已经在这个队列中了（最开始直接扔进去root），然后我们就for循环这个队列的长度就可以了，注意这里一定要用fori循环，并且长度是最开始就给定一个变量。然后每一个i我们都扔掉对头元素，知道遍历玩这一层的。并且在这次遍历中，我们还需要将下一层的扔如队列，这样只要还有元素，队列就不为空。这就是我们为什么需要先定义队列的长度。
    • 然后我们就是判断就可以了。还需要记录一下前一个元素（注意这里在最开始这一层的时候需要进行初始化的）。
• 技巧：
  • 这里有一个很大的技巧，就是fori循环，遍历动态集合，但是通过提前定义size，使得我们可以很方便的对一些东西进行区分。例如，这里可以对层数进行区分。

伪代码

首先判断如果root的val是奇数，直接return false即可。
定义队列treeNodes
添加根节点
定义层数level=第0层
定义前一个节点pre
while循环，条件是队列不等于空
    定义一个变量，来记录是奇数还是偶数
    如果是偶数，那么初始化pre=1000002
  否则为奇数，初始化pre=-1
  定义size，为队列大小，这里跟关键，这个就是表示这一层有多少个元素
  fori循环遍历
    出队
    判断是奇数层还是偶数层
      判断满足的条件：当前节点应该是奇数还是偶数，与前一个是递增还是递减
    左右子节点只要不是空就入队，也就是填充下一层
  层数++

java代码

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        // 层序遍历树，需要用到队列
        if (root.val % 2 == 0) return false;
        LinkedList<TreeNode> treeNodes = new LinkedList<TreeNode>();
        treeNodes.add(root);
        int level = 0;// 层数
        int pre = 0;// 记录每一层前一个节点的值
        while (!treeNodes.isEmpty()) {
            int extra = (level % 2) ^ 1;// 这个是奇数还是偶数的余数
            if (extra == 0) pre = 1000002;// 偶数，取偶数的最大值，因为val不会超过
            else pre = -1;// 奇数，取奇数的最小值，因为val不会超过
            int size = treeNodes.size();// 这一层有多少个节点
            // 接下来遍历这个list中的内容，因为我们还需要往这个list中加，所以这里只能使用fori
            for (int i = 0; i < size; i++) {// 这个for会遍历一层，然后加入下一层
                TreeNode cur = treeNodes.poll();
                if (level % 2 == 0)// 偶数层，递增
                    if (cur.val % 2 != extra || cur.val <= pre) return false;
                    else pre = cur.val;// 更新
                else {
                    if (cur.val % 2 != extra || cur.val >= pre) return false;
                    else pre = cur.val;
                }
                if (cur.left != null) treeNodes.add(cur.left);
                if (cur.right != null) treeNodes.add(cur.right);
            }
            level++;
        }
        return true;
    }
}

• 总结：题目相对复杂，主要是思路理清楚，然后这里一个很重要的技巧就是fori循环的size的使用。我已经见过两次了，上一次是1610题。附上大佬链接。