112.路径总和

题目:112.路径总和

• 示例 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

思路

要判断二叉树中是否存在一条从根节点到叶子节点的路径，使得路径上的节点值相加等于目标和 targetSum，可以使用深度优先搜索（DFS）进行遍历。每次递归时，减去当前节点的值，直到到达叶子节点，判断是否路径上的和等于 targetSum。

• 从根节点开始，递归遍历每个节点。

• 每次访问一个节点时，将 targetSum 减去当前节点的值。

• 如果到达叶子节点时，targetSum 正好为 0，返回 true。

• 如果遍历完整棵树没有找到这样的路径，返回 false。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数

• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

public boolean hasPathSum(TreeNode root, int targetSum) {
    // 如果根节点为空，直接返回false
    if (root == null) {
        return false;
    }
    // 如果是叶子节点，检查当前节点的值是否等于剩余的targetSum
    if (root.left == null && root.right == null) {
        return targetSum == root.val;
    }
    // 递归检查左子树和右子树是否存在符合条件的路径
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}