- LeetCode1609：奇偶树
- 时间：2021-12-25
- 力扣难度：Medium
- 个人难度：Medium
- 数据结构：二叉树
- 算法：BFS、DFS
LeetCode1609.奇偶树：「DFS」&「BFS」
1. 题目描述
题目：原题链接
- 如果一棵二叉树满足下述几个条件，则可以称为奇偶树：
- 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推
- 偶数下标 层上的所有节点的值都是奇整数，从左到右按顺序严格递增
- 奇数下标 层上的所有节点的值都是偶整数，从左到右按顺序严格递减
- 给你二叉树的根节点，如果二叉树为奇偶树 ，则返回 true ，否则返回 false
- 如果一棵二叉树满足下述几个条件，则可以称为奇偶树：
输入输出规范
- 输入：二叉树(根节点)
- 输出：布尔值true或false，表示是否为奇偶树
输入输出示例
输入：
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. 方法一：BFS
思路：广度优先搜索
- 由于判断一棵二叉树是否为奇偶树的条件是针对同一层的节点，因此可以使用广度优先搜索(层序遍历)，每一轮搜索访问同一层的全部节点，且只会访问这一层的节点
- 使用队列存储节点，初始时，将根节点加入队列
- 每一轮搜索之前，队列中的节点是同一层的全部节点，记队列的大小size，该轮搜索只访问size个节点，即可保证该轮搜索访问的恰好是同一层的全部节点
- 搜索过程中，将当前层的节点的非空子节点依次加入队列，用于下一层的搜索
- 在遍历过程中需要记录层下标，并根据层下标检查进行「节点值的奇偶性」和「是否满足递增/递减」
- 奇偶树的判断条件：当前层的各个节点数字的奇偶性、单调性，优先判断不满足的情况
复杂度分析
- 时间复杂度：$O(n)$，其中 n 是二叉树的节点数。广度优先搜索会对每个节点访问一次
- 空间复杂度：$O(n)$，其中 n 是二叉树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过 n
题解
使用一个布尔变量 flag 记录层序是否为偶数，判断节点值的奇偶性
使用 prev 记录当前层的上一节点的值判断是否满足递增/递减，prev 起始值可根据数据范围设置为哨兵值
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// 方法一：BFS
public boolean isEvenOddTreeBFS(TreeNode root) {
if(root == null) return false;
Deque<TreeNode> deque = new ArrayDeque<>();
boolean flag = true; // 标记层数的奇偶性，默认从0(偶数-true)开始, 偶数层要求数字为奇数且递增，奇数层要求数字为偶数且递减
deque.addLast(root);
while (!deque.isEmpty()) {
int size = deque.size();
int prev = flag ? 0 : Integer.MAX_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = deque.pollFirst();
int cur = node.val;
// 偶数层
if(flag && ((cur & 1) == 0 || cur <= prev)) return false;
// 奇数层
if(!flag && ((cur & 1) == 1 || cur >=prev)) return false;
prev = cur;
if(node.left != null) deque.addLast(node.left);
if(node.right != null) deque.addLast(node.right);
}
flag = !flag;
}
return true;
}
3. 方法二：DFS
思路：深度优先搜索
- 深度优先搜索过程中要记录当前层编号(奇偶编号)，用于判断节点值的奇偶性
- 还要记录每层最后上一次遍历到的节点值为多少，用于判断是否满足递增/递减
- 因此需要一个数据结构来保存编号和上次的节点值，一般使用map
复杂度分析
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
题解
同样使用flag标识层数奇偶性，prev标识每一层前一个节点的值
使用Map储存每一层的层号level和对应的最后访问过的节点的值(作为prev)
由于要所有节点都满足才是奇偶树，返回true，所以要将
dfs()方法的递归写在条件中代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// 方法二：DFS
Map<Integer, Integer> map = new HashMap<>();
public boolean isEvenOddTreeDFS(TreeNode root) {
return dfs(root, 0);
}
private boolean dfs(TreeNode root, int level) {
if (root == null) return false;
boolean flag = (level & 1) == 0; // 层数的奇偶性
int prev = map.getOrDefault(level, flag ? 0 : Integer.MAX_VALUE); // 从Map里面获取上次的节点值
int cur = root.val;
// 偶数层
if (flag && ((cur & 1) == 0 || cur <= prev)) return false;
// 奇数层
if (!flag && ((cur & 1) == 1 || cur >= prev)) return false;
map.put(level, cur);
if (root.left != null && !dfs(root.left, level + 1)) return false;
if (root.right != null && !dfs(root.right, level + 1)) return false;
return true;
}
参考资料
- 宫水三叶的题解：https://leetcode-cn.com/problems/even-odd-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-bfs-d-kuyi/
- 官方题解：https://leetcode-cn.com/problems/even-odd-tree/solution/qi-ou-shu-by-leetcode-solution-l7bw/
本文作者：
Chthollists
发布时间： 2021-12-25 18:36:25
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode1609.奇偶树：「DFS」&「BFS」
本文链接： https://chthollists.github.io/post/5504816c.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2021-12-25 18:36:25
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode1609.奇偶树：「DFS」&「BFS」
本文链接： https://chthollists.github.io/post/5504816c.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
