二叉树路径总和怎么判断？为什么只能在叶子节点判定？

简化版

路径总和通常指从根节点到叶子节点的路径和是否等于目标值。做法是 DFS 向下递减 target，到叶子节点时判断剩余值是否等于叶子值，时间 O(n)，递归栈空间 O(h)。

详细版

核心是把“路径和等于 target”转成“走到当前节点时还需要多少”。访问节点 node 时，把 target 减去 node.val，继续递归左右子树；只有当前节点是叶子节点时，才检查 target == node.val，因为题目要求完整的根到叶路径。

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {
        return targetSum == root.val;
    }
    int rest = targetSum - root.val;
    return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
}

不要在中间节点提前返回 true。比如根到某个中间节点已经凑够目标值，但该节点下面还有孩子，这条路径还没有结束，不能算答案。

完整版教学

一、题目真正限定的是“根到叶”

很多同学一看到“路径总和”，会把它理解成树上任意一段路径。面试里最常见的基础版是：路径必须从根节点开始，并且必须走到叶子节点结束。叶子节点的定义是左右孩子都为空，而不是“当前已经满足目标值”。这个限制决定了递归的终止条件：空节点不能构成路径，中间节点不能提前结算。

以这棵树为例：

如果目标值是 9，路径 5 -> 4 的和虽然等于 9，但节点 4 还有左孩子 11，所以它不是根到叶路径，答案仍然不能因为它返回 true。

二、递减 target 比累计 sum 更不容易错

可以从根往下累计 sum，也可以从目标值往下递减。递减写法的好处是叶子节点处的判断非常直接：当前叶子值是否等于剩余目标值。它避免了每层都额外传一个当前和，也减少了回溯时恢复状态的心理负担。

target = 22
5      rest = 17
4      rest = 13
11     rest = 2
2      leaf, 2 == 2, 命中

这条推演对应路径 5 -> 4 -> 11 -> 2，总和正好是 22。递减 target 本质上是在问：“如果要凑成目标值，后面的子树还需要贡献多少？”

三、递归函数的语义要先定清楚

这题的递归函数可以定义为：从 root 出发，是否存在一条根到叶路径，使路径和等于 targetSum。注意这个“根”是当前子树的根，不一定是整棵树的根。只要语义定清楚，递归式就自然出现：当前节点被选中后，剩余目标交给左子树或右子树。

boolean dfs(TreeNode node, int need) {
    if (node == null) return false;
    if (node.left == null && node.right == null) return need == node.val;
    return dfs(node.left, need - node.val) || dfs(node.right, need - node.val);
}

这里的 || 体现了“任意一条路径满足即可”。如果题目要求返回所有路径，就不能只返回布尔值，而要维护路径列表并做回溯。

四、为什么空树返回 false

空树没有任何节点，也就不存在从根到叶的路径。即使目标值是 0，也不能说空路径满足题意。这个边界在面试中经常被追问，因为它能看出候选人是否区分“数值和为 0”与“路径存在”。

输入	target	是否存在路径	原因
空树	0	false	没有根节点，也没有叶子
单节点 5	5	true	根节点同时是叶子
单节点 5	0	false	路径存在但和不等于目标

单节点场景也能验证叶子判断是否写对。根节点没有左右孩子时，它本身就是一条完整路径。

五、复杂度来自访问节点数和树高

最坏情况下每个节点都要访问一次，所以时间复杂度是 O(n)。空间复杂度不是 O(n) 固定值，而是递归调用栈的高度 O(h)。如果树是平衡的，h≈log n；如果退化成链表，h=n。

平衡树:  n=15, h=4
退化树:  n=15, h=15

面试回答时可以说“时间 O(n)，空间 O(h)，最坏 O(n)”。这样比直接说空间 O(n) 更准确，也能体现你知道递归栈和树形形态有关。

六、常见误区与追问

记忆钩子：路径总和基础题的判定点永远在叶子，递归过程只是不断更新“还差多少”。

误区：中间节点凑够目标值就返回 true。 题目限定根到叶，中间节点不是完整路径，不能结算。
误区：遇到空节点时判断 target 是否为 0。 空节点不是叶子，空路径不算合法路径。
误区：负数节点会破坏递减写法。 不会，递减 target 只是等式变形，和正负无关。
追问：如果要返回所有路径怎么办？ 需要维护当前路径列表，到叶子命中时复制一份结果，递归返回时弹出当前节点。
追问：能不能用 BFS？ 可以，队列里同时保存节点和到该节点的累计和或剩余值，遇到叶子再判断。
追问：递归爆栈怎么办？ 对特别深的树可以改成显式栈迭代，空间仍是路径深度级别。

七、加强记忆

把这题记成“三问”：当前节点是否为空，当前节点是否叶子，剩余目标交给谁。空节点没有路径，叶子节点负责最终判定，非叶子节点只负责把 target - node.val 传给左右孩子。只要脑子里抓住“根到叶”和“还差多少”，代码通常就是 4 个分支，边界也不容易乱。

简化版

详细版