跳到主要内容

LeetCode 112. 路径总和

本节目标

沿根到叶路径递减剩余目标值，并只在叶节点判断是否恰好归零。

这是路径状态与结构变换的第一道母题。它要求判断是否存在一条从根节点走到叶节点的路径，使节点值之和等于目标值。

查看 LeetCode 原题

题意与关键边界​

路径必须从根开始、在叶节点结束。若当前节点已经使和达到目标，但它还有孩子，路径还没有结束，不能返回成功。例如树 [5, 1] 的目标为 5 时，根节点不是叶子，答案是 false。

朴素思路与瓶颈​

可以先枚举每一条根到叶路径，再分别累加判断。这样需要额外保存完整路径，并在每个叶子重复计算。题目只需要真假，不需要输出路径，因此无需保存路径容器。

剩余目标不变量​

定义 dfs(node, remaining)：进入 node 前，remaining 是从当前节点到某个叶子还必须凑出的和。进入节点后先减去 node.val；若它是叶子，恰好减为零时成功；否则把更新后的值继续传给左右子树。

整数按值传递，左右递归不会共享可变状态，也就不需要回溯。空节点不可能补齐一条路径，直接返回 false。

正确性依据​

对任意调用 dfs(node, remaining)，扣除当前值后，目标路径剩余部分只能完全位于左子树或右子树。叶节点是唯一允许结束路径的位置，因此叶子处返回 remaining == 0 恰好对应一条合法根到叶路径；非叶节点继续递归不会把中途命中误计为答案。左右子树任一成功时，当前子树就存在合法路径；都失败时不存在。

代码实现​

C++17
class Solution {
private:
    bool dfs(TreeNode* node, int remaining) {
        if (node == nullptr) {
            return false;
        }

        remaining -= node->val;
        if (node->left == nullptr && node->right == nullptr) {
            return remaining == 0;
        }
        return dfs(node->left, remaining) || dfs(node->right, remaining);
    }

public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return dfs(root, targetSum);
    }
};

两份源码都把递归职责命名为 dfs，并只在左右指针都为空时判断剩余目标。它们不读取输入流，树节点由平台提供。

复杂度分析​

最坏情况下访问每个节点一次，时间复杂度为 O(n)。递归调用栈深度为树高 h，额外空间为 O(h)；退化树时为 O(n)，平衡树时为 O(log n)。

边界与易错点​

  • 空树没有根到叶路径，返回 false。
  • 单节点树只在节点值等于目标时返回 true。
  • 负数不改变算法：剩余目标继续相减即可。
  • 不能把“当前累计和已经等于目标”当作成功条件，必须再确认当前节点是叶子。

模式迁移​

若要返回所有满足条件的根到叶路径，就额外维护一个共享 path，进入节点加入、返回时删除。若路径可以从任意节点开始，则不能只传递根路径的剩余目标，需要转向树上前缀和模型。