【面试高频题】难度 2/5，真实面试难度的「树的遍历」运用题

宫水三叶的刷题日记

发布于 2022-05-25 08:26:15

4860

发布于 2022-05-25 08:26:15

文章被收录于专栏：宫水三叶的刷题日记

题目描述

这是 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：

输入：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 <= Node.val <= 10^6

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)

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;
    }
}