树与图简单1 种解法
#112路径总和
判断是否存在一条根到叶子的路径，其节点值之和等于目标值。
#二叉树#深度优先搜索
原题
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题主线
- 向下递归时减去当前节点值，到叶子时检查剩余目标。
解法 1：递归扣减目标
把问题转化为子树是否存在和为 target - node.val 的根到叶路径。
-
时间复杂度： O(n)
-
空间复杂度： O(h)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// 只有叶子才能结束一条根到叶路径，不能在中间节点提前判成功
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
// 递归状态是子树仍需凑出的目标和
int remaining = targetSum - root.val;
// 任一子树存在合法路径即可短路返回
return hasPathSum(root.left, remaining)
|| hasPathSum(root.right, remaining);
}
}边界与易错点
- 必须在叶子节点判断，不能把中途达到目标的非叶节点当作成功。
- 两个来源的相同递归应按题号合并。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q112_113_hasPathSum.javaleetcode/src/main/java/tree/Q112_tree_hasPathSum.java