LeetCode 666. 路径总和 IV
题目描述
题意分析
每个三位数的百位表示深度，十位表示该节点在这一层满二叉树中的位置，个位表示节点值；深度和位置都从 1 开始。要求先计算每条根到叶路径上的节点值之和，再把所有路径和相加。缺失节点不改变其他节点的位置编号。
解法：哈希表 + 深度优先搜索
核心思路
[!blue]
深度和层内位置已经足以定位父子关系，不必再创建树节点。用
depth * 10 + position作键，记录对应节点值。深度为d、位置为p的节点，其左、右孩子分别位于(d + 1, 2p - 1)和(d + 1, 2p)，因为满二叉树中每个父节点按从左到右的顺序占用两个孩子位置。定义
dfs(depth, position, prefixSum)：prefixSum是从根到当前节点父亲的路径和，返回当前子树内所有根到叶路径的总贡献。位置不存在时返回 0；位置存在时，先加上当前节点值，得到currentSum。只有左右孩子都不存在，当前节点才是叶子，此时恰好完成一条路径，返回
currentSum。若至少存在一个孩子，就把同一个currentSum传给两侧，返回左右贡献之和；不存在的一侧贡献 0，不会把未结束的路径另算一次。左右子树的叶子集合互不重叠，因此每条根到叶路径只在自己的叶子处结算一次。共享的祖先值会包含在每条经过它的路径中，符合题目对所有路径分别求和的要求。路径和作为参数传递，两次递归互不修改对方的累计值，无需回溯撤销。
解题步骤
- 对每个编码分别取百位、十位和个位，建立“位置编号 → 节点值”的哈希表。
- 从根位置
(1, 1)开始递归，初始路径和为 0。- 当前位置不存在时返回 0；存在时把节点值加到路径和中。
- 计算左右孩子位置。若都不存在，返回当前路径和。
- 否则分别递归左右孩子，把两侧返回值相加。
代码实现
// 对于深度为 d、位置为 p 的节点，左孩子位置是 2 * p - 1，右孩子位置是 2 * p。
class Solution {
public int pathSum(int[] nums) {
Map<Integer, Integer> values = new HashMap<>();
for (int num : nums) {
int depth = num / 100;
int position = (num / 10) % 10;
int value = num % 10;
values.put(depth * 10 + position, value);
}
return dfs(values, 1, 1, 0);
}
private int dfs(Map<Integer, Integer> values, int depth, int position, int prefixSum) {
int key = depth * 10 + position;
// 不存在的位置贡献零，不能把未完成路径当作答案
if (!values.containsKey(key)) {
return 0;
}
int currentSum = prefixSum + values.get(key);
int nextDepth = depth + 1;
int leftPosition = position * 2 - 1;
int rightPosition = position * 2;
int leftKey = nextDepth * 10 + leftPosition;
int rightKey = nextDepth * 10 + rightPosition;
if (!values.containsKey(leftKey) && !values.containsKey(rightKey)) {
// 只有自身两个孩子都不存在，才结算一条根到叶路径
return currentSum;
}
return dfs(values, nextDepth, leftPosition, currentSum)
+ dfs(values, nextDepth, rightPosition, currentSum);
}
}
// 对于深度为 d、位置为 p 的节点，左孩子位置是 2 * p - 1，右孩子位置是 2 * p。
func pathSum(nums []int) int {
values := make(map[int]int, len(nums))
for _, num := range nums {
depth := num / 100
position := (num / 10) % 10
value := num % 10
values[depth*10+position] = value
}
var dfs func(depth int, position int, prefixSum int) int
dfs = func(depth int, position int, prefixSum int) int {
key := depth*10 + position
value, exists := values[key]
// 不存在的位置贡献零，不能把未完成路径当作答案
if !exists {
return 0
}
currentSum := prefixSum + value
nextDepth := depth + 1
leftPosition := position*2 - 1
rightPosition := position * 2
leftKey := nextDepth*10 + leftPosition
rightKey := nextDepth*10 + rightPosition
if _, hasLeft := values[leftKey]; !hasLeft {
if _, hasRight := values[rightKey]; !hasRight {
// 只有自身两个孩子都不存在，才结算一条根到叶路径
return currentSum
}
}
return dfs(nextDepth, leftPosition, currentSum) + dfs(nextDepth, rightPosition, currentSum)
}
return dfs(1, 1, 0)
}
复杂度分析
- 时间复杂度：期望 $O(n)$，其中 $n$ 是编码数量。建表处理每个编码一次，递归访问每个节点及其孩子位置常数次。
- 空间复杂度：$O(n)$，哈希表保存全部节点。递归栈占 $O(h)$，本题树深度最多为 4。
关键点总结
[!green]
- 层内位置沿用满二叉树编号，由此直接推导孩子坐标。
- 递归参数携带路径和，返回值累加叶子贡献，两者含义不同。
- 只有真正的叶子才结算路径，空孩子直接贡献 0。
易错点总结
[!yellow]
- 不能按输入中实际出现的次序重新编号节点，否则缺失位置会使父子关系错乱。
- 位置从 1 开始，孩子位置是
2p - 1、2p，不能套用从 0 开始的数组下标公式。- 节点值允许为 0，必须检查键是否存在，不能用取出的值是否为 0 判断节点存在。
- 叶子由自身两个孩子是否存在决定，不能仅看它是否位于全树最深一层。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 112. 路径总和 | 简单 | 可先由层号和位置还原父子关系，再复用根到叶路径和递推；本题最终累加全部路径的和。 |
| 257. 二叉树的所有路径 | 简单 | 同样遍历所有根到叶路径，本题只保存累计和而非完整路径文本。 |
| 113. 路径总和 II | 中等 | 路径总和系列。都在 DFS 中维护根到当前节点的累加和；II 还需保存路径并按目标和筛选。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！