题目描述
这是 LeetCode 上的「1609. 奇偶树」，难度为「中等」。
Tag : 「层序遍历」、「BFS」、「DFS」
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 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：
代码语言：javascript复制输入：root = [1]
输出：true
示例 5：
代码语言：javascript复制输入：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 起始值可根据数据范围设置为哨兵值。
代码：
代码语言：javascript复制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 过程中除了要记录当前层编号（判断节点值的奇偶性），还要记录每层最后上一次遍历到的节点值为多少（判断是否满足递增/递减）。
代码：
代码语言：javascript复制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 原题链接和其他优选题解。
