网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 1609. 奇偶树 ，难度为 中等。
Tag : 「层序遍历」、「BFS」、「DFS」
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 00 ，根的子节点所在层下标为 11 ，根的孙节点所在层下标为 22 ，依此类推。
- 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
- 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 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,105] 内
- 1 <= Node.val <= 10^61<=Node.val<=106
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)
- 空间复杂度：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)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1609 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
