题目形容

这是 LeetCode 上的 1302. 层数最深叶子节点的和 ，难度为 中等。

Tag : 「DFS」、「BFS」、「树的遍历」

给你一棵二叉树的根节点 root，请你返回 层数最深的叶子节点的和 。

示例 1：

输出：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]输入：15

示例 2：

输出：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]输入：19

提醒：

  • 树中节点数目在范畴 $[1, 10^4]$ 之间。
  • $1 <= Node.val <= 100$

BFS

应用 BFS 进行树的遍历，处理过程中记录最大深度 depth 以及应用哈希表记录每层元素和。

Java 代码：

class Solution {    public int deepestLeavesSum(TreeNode root) {        Map<Integer, Integer> map = new HashMap<>();        Deque<TreeNode> d = new ArrayDeque<>();        d.addLast(root);        int depth = 0;        while (!d.isEmpty()) {            int sz = d.size();            while (sz-- > 0) {                TreeNode node = d.pollFirst();                map.put(depth, map.getOrDefault(depth, 0) + node.val);                if (node.left != null) d.addLast(node.left);                if (node.right != null) d.addLast(node.right);            }            depth++;        }        return map.get(depth - 1);    }}

TypeScript 代码：

function deepestLeavesSum(root: TreeNode | null): number {    const map: Map<number, number> = new Map<number, number>()    const stk: TreeNode[] = new Array<TreeNode>(10010)    let he = 0, ta = 0, depth = 0    stk[ta++] = root    while (he < ta) {        let sz = ta - he        while (sz-- > 0) {            const node = stk[he++]            if (!map.has(depth)) map.set(depth, 0)            map.set(depth, map.get(depth) + node.val)            if (node.left != null) stk[ta++] = node.left            if (node.right != null) stk[ta++] = node.right        }        depth++    }    return map.get(depth - 1)};
  • 工夫复杂度：$O(n)$
  • 空间复杂度：$O(n)$

DFS

应用 DFS 进行树的遍历，处理过程中记录最大深度 depth 以及应用哈希表记录每层元素和。

Java 代码：

class Solution {    Map<Integer, Integer> map = new HashMap<>();    int max;    public int deepestLeavesSum(TreeNode root) {        dfs(root, 0);        return map.get(max);    }    void dfs(TreeNode root, int depth) {        if (root == null) return ;        max = Math.max(max, depth);        map.put(depth, map.getOrDefault(depth, 0) + root.val);        dfs(root.left, depth + 1);        dfs(root.right, depth + 1);    }}

TypeScript 代码：

const map: Map<number, number> = new Map<number, number>()let max: numberfunction deepestLeavesSum(root: TreeNode | null): number {    map.clear()    max = 0    dfs(root, 0)    return map.get(max)};function dfs(root: TreeNode | null, depth: number): void {    if (root == null) return     max = Math.max(max, depth)    if (!map.has(depth)) map.set(depth, 0)    map.set(depth, map.get(depth) + root.val)    dfs(root.left, depth + 1)    dfs(root.right, depth + 1)}
  • 工夫复杂度：$O(n)$
  • 空间复杂度：$O(n)$

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

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

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布