Path Sum
你会得到一个按层序存储在数组 tree 中的二叉树，以及一个数字 targetSum。根节点位于索引 0，索引 i 处节点的子节点位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，并且数组末尾可能有多余的 -1 项。如果从根节点向下到某个叶节点的路径上，各节点的值之和等于 targetSum，则返回 true，否则返回 false。叶节点是两个子节点位置都为空的节点。
函数
- treeinteger-array
- 按层序遍历二叉树，空位置用 -1 表示
- targetSuminteger
- 根到叶路径必须达到的总和
- 返回值boolean
- 如果某条从根到叶子的路径之和等于 targetSum，则为 true，否则为 false。
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或者是一个满足0 ≤ tree[i] ≤ 1000的值。 tree[0]永远不会是-1，所以这棵树至少有一个节点。- 数组在最后一个节点之后可能还会有额外的
-1项。 - 空位置的两个子节点也都是空的，深度最多为
14。 0 ≤ targetSum ≤ 15000
示例
- 输入
- tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
- 输出
- true
- 解释
- 路径
3、9、2（索引0、1、4）的和是14，索引4处的2是一个叶节点。
- 输入
- tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
- 输出
- false
- 解释
3 + 9 = 12，但9有一个子节点，所以没有路径在这里结束。三条从根节点到叶节点的路径之和分别是14、10和16，都不是12。
- 输入
- tree = [4, -1, -1]targetSum = 4
- 输出
- true
- 解释
- 根节点的两个子节点位置都是空的，因此根节点本身就是叶节点。只包含
4的路径之和为4。
进阶
如果一条路径可以从任意节点开始，并在其下方的任意节点结束，你能数出总和为 targetSum 的路径有多少条吗？
提示
逐个打开提示，每个都会多透露一点。
从根节点向下遍历，并持续累加总和。你可以在哪里将这个总和与
targetSum进行比较？只有在叶节点处，也就是两个子节点位置都为空的节点处，才算结束路径。只有一个子节点的节点不会结束路径，即使总和已经匹配也是如此。将当前路径的和继续传递给每个子节点。
维护一个由节点索引和从根节点到该节点的总和组成的数对栈。弹出一个数对；如果该节点是叶节点，且总和等于
targetSum，则返回true。否则，将每个实际子节点及其值加到总和后的结果一起入栈。
题解
只有从根节点到叶节点的完整路径才算数。累计和可能会在一个仍有子节点的节点处达到 targetSum，但这不算。因此，要把路径的和作为参数或放在栈中传递到每个节点，并且只在叶节点处将其与目标值比较。
对剩余总和进行递归
思路
一条总和为 targetSum 的路径从根节点的值开始，因此路径剩余部分从根节点的某个子节点开始，其总和必须等于 targetSum 减去根节点的值。这是同一个问题，只不过树更小。沿着路径向下时，减去每个节点的值；到达叶节点时，路径结束，因此答案取决于是否恰好没有剩余值。
在第一个示例中，根节点减去 3 后剩下 14 - 3 = 11，9 减去后剩下 2，叶节点 2 减去后剩下 0。在第二个示例中，9 减去后已经剩下 0，但它还有一个子节点，所以搜索会继续。每个节点只访问一次，时间复杂度为 O(n)，调用栈每层保存一个栈帧，最多为 15 个。
算法
- 编写
walk(i, remaining)，并从remaining中减去tree[i]。 - 如果
i的两个子节点位置都为空（索引超出末尾或为-1），则返回remaining是否为0。 - 否则，如果对实际存在的左子节点或右子节点调用
walk后返回true，则返回true。 - 返回
walk(0, targetSum)。
def hasPathSum(tree, targetSum):
n = len(tree)
def walk(i, remaining):
# remaining is what the path still needs once it reaches node i.
remaining -= tree[i]
left, right = 2 * i + 1, 2 * i + 2
has_left = left < n and tree[left] != -1
has_right = right < n and tree[right] != -1
if not has_left and not has_right:
return remaining == 0 # a leaf: the path ends here
return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))
return walk(0, targetSum)使用显式栈的深度优先搜索
思路
递归会在每次调用时保存一个数字。你可以自己保存这个数字，把它和每个节点放在一起，存入栈中：这个数字是从根节点到该节点的路径总和。从 (0, tree[0]) 开始；每个子节点的总和等于其父节点的总和加上它自己的值。弹出一对值。如果该节点是叶节点，且总和为 targetSum，就完成了；否则，将它实际存在的子节点压入栈中。
每个实际存在的节点只会被压入一次，时间复杂度为 O(n)，栈中每层大约会有一个等待处理的兄弟节点，空间复杂度为 O(h)。同样的循环也适用于基于指针的深层树，而递归可能会耗尽栈空间。
算法
- 将
(0, tree[0])入栈。 - 弹出一对
(i, total)，并查看子节点位置2*i+1和2*i+2。 - 如果两个子节点都不存在，并且
total等于targetSum，则返回true。 - 将每个存在的子节点
c以(c, total + tree[c])的形式入栈。 - 当栈为空时，返回
false。
def hasPathSum(tree, targetSum):
n = len(tree)
stack = [(0, tree[0])] # (node index, sum of the path from the root to it)
while stack:
i, total = stack.pop()
left, right = 2 * i + 1, 2 * i + 2
has_left = left < n and tree[left] != -1
has_right = right < n and tree[right] != -1
if not has_left and not has_right and total == targetSum:
return True # a leaf whose path adds up
if has_left:
stack.append((left, total + tree[left]))
if has_right:
stack.append((right, total + tree[right]))
return False
易错点和边界情况
- 在每个节点比较总和。在第二个示例中，
3 + 9 = 12在9处匹配，但9有一个子节点，所以答案是false。 - 让空的子节点位置结束一条路径。这样，第二个示例中的
9会通过它的空左子节点位置结束一条路径。 - 忘记单独的根节点。单个节点就是叶节点，所以目标值为
4时，[4]的结果是true；目标值为0时，[0]的结果也是如此。 - 读取超出数组末尾的位置。靠近末尾的叶节点可能有超出最后一个条目的子节点索引。
- 混淆 Lua 和 R 中的偏移量。对于
2*i+1，节点索引保持从 0 开始，并读取tree[i + 1]。
常见问题3
路径和的时间复杂度是多少？
O(n)：每个节点最多访问一次，搜索可以在找到第一个匹配的叶节点时停止。额外空间为 O(h)，用于存储正在探索的路径，可以通过调用栈帧或你自己的栈中的条目来实现。
可以用 BFS 解决路径和问题吗？
是的。把节点及其路径和组成的配对放入队列，而不是栈中，并在每个叶节点出队时进行检查。时间复杂度仍为 O(n)，但队列可能容纳整整一层的节点，也就是满二叉树中大约一半的节点；而栈中每层大约只存一个节点。
如何找出所有总和等于目标值的路径？
向下遍历时，保留当前路径上的节点列表；每当到达总和匹配的叶节点时，就将路径复制到答案中；向上回溯时，移除最后一个节点。遍历过程保持不变。当有许多叶节点匹配时，复制路径的开销可能比遍历本身更大。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def hasPathSum(tree, targetSum):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [3, 9, 6, -1, 2, 1, 7] targetSum = 14
预期输出
true