树与图简单1 种解法

#112路径总和

判断是否存在一条根到叶子的路径，其节点值之和等于目标值。

#二叉树#深度优先搜索

解题主线

向下递归时减去当前节点值，到叶子时检查剩余目标。

解法 1：递归扣减目标

把问题转化为子树是否存在和为 target - node.val 的根到叶路径。

时间复杂度

O(n)

空间复杂度

O(h)

112. 路径总和 · 递归扣减目标

java

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);
    }
}

把问题转化为子树是否存在和为 target - node.val 的根到叶路径。

边界与易错点

必须在叶子节点判断，不能把中途达到目标的非叶节点当作成功。
两个来源的相同递归应按题号合并。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q112_113_hasPathSum.javaleetcode/src/main/java/tree/Q112_tree_hasPathSum.java