奇偶树
难度:
标签:
题目描述
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
- 二叉树根节点所在层下标为
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, 105]内 1 <= Node.val <= 106
代码结果
运行时间: 190 ms, 内存: 0.0 MB
/*
思路：
1. 由于Java的Stream API不适合直接处理二叉树的遍历，这里先使用BFS遍历树，将每一层的节点值收集为List。
2. 对于每一层使用Stream API进行奇偶性检查和顺序检查。
3. 如果发现任何一层不满足条件，返回false；否则，返回true。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean isEvenOddTree(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
List<Integer> levelValues = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
levelValues.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
boolean valid = level % 2 == 0 ?
levelValues.stream().allMatch(v -> v % 2 != 0) &&
IntStream.range(1, levelValues.size()).allMatch(i -> levelValues.get(i) > levelValues.get(i - 1)) :
levelValues.stream().allMatch(v -> v % 2 == 0) &&
IntStream.range(1, levelValues.size()).allMatch(i -> levelValues.get(i) < levelValues.get(i - 1));
if (!valid) return false;
level++;
}
return true;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}解释
方法:
该解法使用宽度优先搜索（BFS）来遍历二叉树的各层。使用一个队列来存储当前层的所有节点，并使用一个布尔变量 `isEvenLevel` 来标记当前层是否是偶数层。对于每层，我们使用一个变量 `prevVal` 来记录前一个节点的值以便进行比较。对于偶数层，所有节点的值应为奇数且严格递增；对于奇数层，所有节点的值应为偶数且严格递减。如果任何节点不符合这些条件，函数立即返回 `false`。如果成功遍历完整棵树，则返回 `true`。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中，如何确保每一层的节点值都是按照题目要求的顺序（偶数层严格递增，奇数层严格递减）进行检查的？
▷🦆
为什么在判断节点值是否符合当前层级要求时，使用了`prevVal < currVal`和`prevVal > currVal`的条件？
▷🦆
在BFS遍历中，节点值的奇偶性检查（`currVal % 2 == 1`或`currVal % 2 == 0`）为何要与节点值的比较顺序（递增或递减）同时进行？
▷🦆
为什么在处理每一层的节点时使用了`prevVal`初始化为`0`或`float('inf')`，这种初始化方式对算法的正确性有什么影响？
▷