026 · Path Sum

My First Thoughts

这道题问的是：有没有一条从根节点到叶子节点的路径，路径上所有节点的值加起来正好等于 targetSum。

先看最基本的情况。

如果 root is None，说明是一棵空树，没有任何根到叶子的路径，应该返回 False：

if root is None:
    return False

接下来会自然想到一个方向：与其一路把节点值加起来再和 targetSum 比较，不如反过来，把 targetSum 一路减下去。

每经过一个节点，就把它的值从目标里减掉：

target -= root.val

减完之后，剩下的 target 就是“后面还需要凑出多少”，相当于一个新的目标继续往下传。

顺着这个思路，第一反应是想提前剪枝。既然是在做减法，如果某一步 target 已经被减成负数了，是不是就说明这条路走过头了，可以直接返回 False：

target -= root.val
if target < 0:
    return False

这样感觉能少走很多冤枉路。

另外一开始还想过参考 Two Sum 那种“记录见过的值”的做法，用一个哈希表存下沿途的和。

把这些拼起来，大概的雏形就是：

def hasPathSum(root, target):
    if root is None:
        return False

    target -= root.val
    if target < 0:
        return False

    return hasPathSum(root.left, target) or hasPathSum(root.right, target)

方向上，“把 target 一路减下去，到叶子看是否归零”这个核心是对的。但里面藏着两个问题。

---

Why That Is Not Enough

第一个问题是 Two Sum 的思路在这里用不上。

Two Sum 要做的是在一堆数里找“任意两个数配对”，所以需要哈希表记录见过的数。但这道题是一条确定的路径从头加到尾，节点之间没有“配对”关系，只是单纯地累减。所以根本不需要哈希表。

第二个问题更关键，是那个 target < 0 的剪枝。

看一眼题目的约束：

-1000 ≤ Node.val ≤ 1000

节点的值可以是负数。

一旦节点可以是负数，“target 减到负数就提前返回 False”就是错的。因为后面如果还有负节点，会把 target 又加回来。

举个例子：

    5
     \
     -3
       \
        1

如果 targetSum = 3，正确路径是 5 -> -3 -> 1，和正好是 3。

但按提前剪枝的写法，走到 5 时 target = 3 - 5 = -2，已经小于 0，会被直接判成 False，于是漏掉了这条本来正确的路径。

所以这道题不能提前退出。在没走到叶子节点之前，谁也不知道后面会不会被负数救回来，只能老老实实把每条路走到底。

还有一个一直纠结的点是 target 的“作用域”：往下走的时候，左分支和右分支用的好像都是同一个 target，那左边改了会不会影响右边？

其实在递归里这不是问题。target - root.val 只是一个传给子调用的参数值，左子树拿到自己的一份，右子树拿到自己的一份，互不影响。不需要任何额外的对象去“装”某个分支的值，也不需要一个全局的标志位来协调左右。每一层、每个分支天然各有一份独立的 target。

把这两点想清楚之后，正解就很简单了。

---

Final Idea

正确的写法只需要把“何时判断成功”这件事放对位置。

先处理空树：

if root is None:
    return False

然后是关键的一步：处理叶子节点。

叶子节点没有左孩子也没有右孩子。走到叶子节点时，这条路径就到头了，这时才去判断剩下的目标是不是正好等于当前这个叶子的值：

if root.left is None and root.right is None:
    return targetSum == root.val

注意这里判断的位置。题目要求路径必须走到叶子节点才算完整，不能中途停。所以“是否凑够”这件事，只在叶子节点判断。

为什么不直接在 root is None 那里判断 targetSum == 0？

因为 root is None 表示的是“这里没有节点”，它本身不是一条有效的根到叶子路径。这一点和上一题 Minimum Depth 是同一个坑：空节点返回的那个值只代表“这里是空的”，不代表已经找到了一条完整路径。如果在空节点判断 targetSum == 0，一个只有单边孩子的节点就可能在那个空的方向上被误判成功。

把判断放在叶子节点，才真正对应“走到叶子才算数”。

最后是中间节点。当前节点不是叶子，就把它的值从目标里减掉，然后左右子树只要有一条能凑出剩下的目标，整条路径就成立：

return hasPathSum(root.left, targetSum - root.val) \
    or hasPathSum(root.right, targetSum - root.val)

这里用 or 正好解决了之前纠结的“一个分支不行、另一个分支怎么办”的问题：只要任意一边成立就返回 True，两边都不成立才返回 False。完全不需要自己去维护标志位。

单边孩子的情况也被这个 or 自然处理了。比如某个节点只有右孩子，那么左边 hasPathSum(None, ...) 会返回 False，or 就会去看右边那条真正的路径。

---

Why It Works

递归函数 hasPathSum(root, targetSum) 的含义是：

从 root 出发，存不存在一条到叶子节点的路径，使路径上的值之和等于 targetSum。

空节点没有任何路径，所以返回 False。

叶子节点是路径的终点，这条路径能否成立，就看减到这里剩下的目标是否正好等于叶子的值，所以返回 targetSum == root.val。

中间节点自己先消耗掉一部分目标，剩下的 targetSum - root.val 交给左右子树去继续凑。只要任意一棵子树里存在这样一条路径，经过当前节点的整条路径就成立，所以用 or 把左右结果合起来。

因为递归会走到每一条从根到叶子的路径，并且只在叶子节点才下结论，所以不会漏掉任何一条路径，也不会在中途错误地提前结束。节点是不是负数都没关系，因为全程没有依赖“目标必须单调减小”这种假设。

---

Code

def hasPathSum(root, targetSum):
    if root is None:
        return False

    if root.left is None and root.right is None:
        return targetSum == root.val

    remaining = targetSum - root.val
    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

---

Complexity

Time	\(O(n)\) - 最坏情况下需要访问树中的每个节点一次
Space	\(O(h)\) - 递归调用栈的深度等于树的高度 h，最坏情况下可以到 \(O(n)\)

---

Takeaway

这题最容易踩的坑是把它当成“目标在做减法，所以减到负数就能提前剪枝”。但只要节点值可以是负数，这个前提就不成立，必须把每条路走到叶子才能下结论。另外要分清判断成功的位置：只能在叶子节点判断 targetSum == root.val，而不是在空节点判断 targetSum == 0。空节点只表示“没有节点”，不是一条有效的根到叶子路径。

---

← Quiz