LeetCode 112. 路径总和

2026-04-14 HGNULB 约 4 分钟

文章信息 16 个分类 6 个标签

分类

LeetCode CodeTop 简单已解决已掌握 50-100 字节跳动美团快手腾讯猿辅导滴滴商汤虾皮携程面试经典 150 题

题目描述

✅ 112. 路径总和

题意分析

给定二叉树的根节点和目标和 targetSum，判断树中是否存在一条从根节点到叶子节点的路径，使路径上所有节点值之和恰好等于目标值。只需回答存在与否，不需要给出具体路径。

「根到叶」是本题最强的约束：路径必须从根出发、必须在叶子（没有任何孩子的节点）结束，停在中间节点不算，从中间某节点出发也不算。因此判等的时机只有一个——走到叶子的那一刻。

边界信号有两个：其一，题目明确约定空树没有任何路径，即使 targetSum 为 0 也应返回 false；其二，节点值范围是 [-1000, 1000]，可以为负，这意味着路径和不单调，不能凭「和已经超了」提前下结论。

解法：DFS 递减剩余路径和

核心思路

问题关键：题目要求的是“根到叶子”的完整路径，只有到达叶子时才能判断路径和；中间节点即使当前和等于目标也不能提前成功。

为什么选 DFS：每条候选路径都从根沿父子关系向下，DFS 正好逐层处理。题目只判断是否存在，不需要保存整条路径；访问当前节点时从目标值中减去节点值，把剩余目标交给子树即可。

递归不变量：hasPathSum(node, remain) 表示“从 node 到某个叶子的路径能否凑出 remain”。若 node 是叶子，只需判断 remain == node.val；否则递归检查左右子树能否凑出 remain - node.val。任一子树成功即可短路返回。

解题步骤

当前节点为空时返回 false，空节点不构成路径终点。

当前节点是叶子时，直接判断剩余目标是否等于叶子值。

非叶节点先计算 remain = targetSum - root.val。

分别递归左右子树并用逻辑或连接，只要存在一条合法路径即可。

例如目标值为 22 时，路径 5 → 4 → 11 → 2 依次把剩余值变为 17 → 13 → 2，到叶子 2 时匹配成功。

代码实现

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        int remain = targetSum - root.val;
        return hasPathSum(root.left, remain) || hasPathSum(root.right, remain);
    }
}

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return targetSum == root.Val
    }

    remain := targetSum - root.Val
    return hasPathSum(root.Left, remain) || hasPathSum(root.Right, remain)
}

复杂度分析

时间复杂度：$O(n)$，最坏情况下访问每个节点一次。

空间复杂度：$O(h)$，h 为树高；平衡树为 $O(\log n)$，链状树为 $O(n)$。

关键点总结

先定义递归函数语义，再写“空节点、叶子、递归”三个分支，代码自然对应证明。

叶子必须同时满足左右孩子为空，只有一个孩子的节点不是叶子。

节点值可能为负数，剩余目标小于 0 时不能剪枝。

若追问输出具体路径，需要增加路径列表并回溯；本题只判存在，因此无需保存路径。

易错点总结

在空节点处判断 targetSum == 0：树 [1,2]、目标 1 会沿根的空右孩子误判成功；空节点必须返回 false。

在中间节点提前判相等：树 [1,2]、目标 1 的根不是叶子，正确答案仍是 false。

叶子条件写成 left == null || right == null：只有一个孩子的节点会被误当叶子，应使用 &&。

剩余目标为负时提前返回：节点值允许为负，路径 [1,-2] 仍可能凑出 -1。

相似题目

题目	难度	考察点
113. 路径总和 II	中等	从判存在升级为回溯收集所有具体路径
129. 求根节点到叶节点数字之和	中等	沿路径乘 10 累积数字，叶子处汇总
257. 二叉树的所有路径	简单	根到叶路径的字符串拼接输出
404. 左叶子之和	简单	叶子判定的变体，只统计作为左孩子的叶子
437. 路径总和 III	中等	起点不限于根，前缀和加哈希计数
1022. 从根到叶的二进制数之和	简单	129 的二进制版本，移位累积
LCR 049. 求根节点到叶节点数字之和	中等	129 的 LCR 镜像题
剑指 Offer 34. 二叉树中和为某一值的路径	中等	113 的剑指 Offer 版本