路径总和

难度: Easy

给你二叉树的根节点 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

Submission

运行时间: 44 ms

内存: 16.6 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        if root.left is None and root.right is None:
            return root.val == targetSum
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

Explain

这个题解采用递归的方式来判断是否存在根节点到叶子节点的路径，其和等于目标值。具体思路如下： 1. 如果当前节点为空，返回False，因为空树不存在满足条件的路径。 2. 如果当前节点是叶子节点（即左右子节点都为空），判断当前节点的值是否等于目标值，如果相等则找到了一条满足条件的路径，返回True；否则返回False。 3. 如果当前节点不是叶子节点，则递归地在其左子树和右子树中查找是否存在满足条件的路径。在递归时，将目标值减去当前节点的值，这样就可以在子树中继续判断剩余的目标值是否能够由根节点到叶子节点的路径所满足。 4. 如果在左子树或右子树中任一找到满足条件的路径，就返回True；只有当左右子树都不存在满足条件的路径时，才返回False。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        # 如果当前节点为空，返回False
        if root is None:
            return False
        
        # 如果当前节点是叶子节点，判断节点值是否等于目标值
        if root.left is None and root.right is None:
            return root.val == targetSum
        
        # 递归判断左子树和右子树是否存在满足条件的路径
        # 在递归时，将目标值减去当前节点的值
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

Explore

即使当前节点的值大于当前目标和，仍然有必要继续探索该节点的子树。这是因为子树中的节点值可以是负数，这样的负值节点可能会帮助达到目标和。因此，不能仅基于当前节点的值与目标和的比较就决定停止探索。

递归时减去当前节点的值意味着每向下递归一层，目标和会相应调整。如果节点值为负，实际上是增加了递归到该节点子树时的目标和。这种处理方式可以正确处理包含负值节点的情况，因为它允许在路径上累加负数，可能正是因为这些负数的存在，才使得路径总和达到了目标值。

递归解法在理论上对于非常大或非常小的targetSum值仍然有效，因为Python的整数类型支持大整数计算，不会像某些语言那样有固定的整数溢出问题。然而，实际应用中如果数值过大，可能会导致性能问题，尤其是在深度较大的递归过程中，可能会导致执行时间过长或者内存使用过高。

在递归函数中，如果左子树已经找到了满足条件的路径，那么就没有必要继续检查右子树了。这是因为题目只要求判断是否存在至少一条满足条件的路径。一旦找到这样一条路径，就可以立即返回True，结束所有进一步的搜索。