LC 1302. 层数最深叶子节点的和

题目描述

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

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

示例 1:

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

输出:15

示例 2:
1
2
3
输入: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 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const map: Map<number, number> = new Map<number, number>()
let max: number
function 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/SharingSource/LogicStack-LeetCode

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


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!