LC 515. 在每个树行中找最大值

题目描述

这是 LeetCode 上的 515. 在每个树行中找最大值 ，难度为 中等。

给定一棵二叉树的根节点 root，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]

输出: [1,3,9]

示例2：

输入: root = [1,2,3]

输出: [1,3]

提示：

• 二叉树的节点个数的范围是 $[0,10^4]$
• $-2^{31} <= Node.val <= 2^{31} - 1$

---

BFS

使用 BFS 进行层序遍历，单次 BFS 逻辑将整一层的元素进行出队，维护当前层的最大值，并将最大值加入答案。

代码：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            int sz = d.size(), max = d.peek().val;
            while (sz-- > 0) {
                TreeNode node = d.pollFirst();
                max = Math.max(max, node.val);
                if (node.left != null) d.addLast(node.left);
                if (node.right != null) d.addLast(node.right);
            }
            ans.add(max);
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

DFS

同理，可以借助 DFS 进行求解，在 DFS 整棵树时，同时传递一个当前层深度 depth，使用「哈希表」维护所有深度的最大节点值，同时使用变量 max 记录最大深度。

结束 DFS 后，使用哈希表构造答案。

代码：

class Solution {
    int max = 0;
    Map<Integer, Integer> map = new HashMap<>();
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 1);
        for (int i = 1; i <= max; i++) ans.add(map.get(i));
        return ans;
    }
    void dfs(TreeNode node, int depth) {
        if (node == null) return ;
        max = Math.max(max, depth);
        map.put(depth, Math.max(map.getOrDefault(depth, Integer.MIN_VALUE), node.val));
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.515 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。