LC 1609. 奇偶树

题目描述

这是 LeetCode 上的 1609. 奇偶树 ，难度为 中等。

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

二叉树根节点所在层下标为 $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, 10^5]$ 内
• $1 <= Node.val <= 10^6$

---

BFS

考察「层序遍历」，在遍历过程中需要记录层下标，并根据层下标检查进行「节点值的奇偶性」和「是否满足递增/递减」。

额外使用一个布尔变量 flag 记录层序是否为偶数（判断节点值的奇偶性），使用 prev 记录当前层的上一节点的值（判断是否满足递增/递减）即可，prev 起始值可根据数据范围设置为哨兵值。

代码：

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Deque<TreeNode> d = new ArrayDeque<>();
        boolean flag = true;
        d.addLast(root);
        while (!d.isEmpty()) {
            int size = d.size(), prev = flag ? 0 : 0x3f3f3f3f;
            while (size-- > 0) {
                TreeNode node = d.pollFirst();
                int cur = node.val;
                if (flag && (cur % 2 == 0 || cur <= prev)) return false;
                if (!flag && (cur % 2 != 0 || cur >= prev)) return false;
                prev = cur;
                if (node.left != null) d.addLast(node.left);
                if (node.right != null) d.addLast(node.right);
            }
            flag = !flag;
        }
        return true;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

DFS

同样的思路，自然也能够使用 DFS 进行求解。

由于 DFS 是深度优先，因此我们在 DFS 过程中除了要记录当前层编号（判断节点值的奇偶性），还要记录每层最后上一次遍历到的节点值为多少（判断是否满足递增/递减）。

代码：

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public boolean isEvenOddTree(TreeNode root) {
        return dfs(root, 0);
    }
    boolean dfs(TreeNode root, int idx) {
        boolean flag = idx % 2 == 0;
        int prev = map.getOrDefault(idx, flag ? 0 : 0x3f3f3f3f), cur = root.val;
        if (flag && (cur % 2 == 0 || cur <= prev)) return false;
        if (!flag && (cur % 2 != 0 || cur >= prev)) return false;
        map.put(idx, root.val);
        if (root.left != null && !dfs(root.left, idx + 1)) return false;
        if (root.right != null && !dfs(root.right, idx + 1)) return false;
        return true;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1609 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。