-
每日一题：LeetCode：1609.奇偶树
时间：2021-12-25
力扣难度：Medium
个人难度：Medium
数据结构：二叉树
算法：BFS、DFS
2021-12-25：LeetCode：1609.奇偶树
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 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树
LC1609奇偶树-题目.jpg
2. 方法一：BFS
-
思路：广度优先搜索
由于判断一棵二叉树是否为奇偶树的条件是针对同一层的节点，因此可以使用广度优先搜索(层序遍历)，每一轮搜索访问同一层的全部节点，且只会访问这一层的节点
使用队列存储节点，初始时，将根节点加入队列
每一轮搜索之前，队列中的节点是同一层的全部节点，记队列的大小size，该轮搜索只访问size个节点，即可保证该轮搜索访问的恰好是同一层的全部节点
搜索过程中，将当前层的节点的非空子节点依次加入队列，用于下一层的搜索
在遍历过程中需要记录层下标，并根据层下标检查进行「节点值的奇偶性」和「是否满足递增/递减」
奇偶树的判断条件：当前层的各个节点数字的奇偶性、单调性，优先判断不满足的情况
-
复杂度分析
时间复杂度：
，其中 n 是二叉树的节点数。广度优先搜索会对每个节点访问一次
空间复杂度：
-
题解
使用一个布尔变量 flag 记录层序是否为偶数，判断节点值的奇偶性
使用 prev 记录当前层的上一节点的值判断是否满足递增/递减，prev 起始值可根据数据范围设置为哨兵值
-
代码
// 方法一：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
-
复杂度分析
时间复杂度：
空间复杂度：
-
题解
同样使用flag标识层数奇偶性，prev标识每一层前一个节点的值
使用Map储存每一层的层号level和对应的最后访问过的节点的值(作为prev)
由于要所有节点都满足才是奇偶树，返回true，所以要将
dfs()方法的递归写在条件中-
代码
// 方法二：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; }
