路径总和

🎯 问题描述（来源于LeetCode）

描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。
如果存在，返回 true；否则，返回 false。

说明：

  • 叶子节点是指没有子节点的节点。

  • 路径必须是从根节点出发，一直走到叶子节点。

  • 示例：

    • 示例 1：
      1
      2
      3
      输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
      输出：true
      解释：存在一条根节点到叶子节点的路径 5 -> 4 -> 11 -> 2，和为 22。
    • 示例 2：
      1
      2
      3
      4
      5
      6
      输入：root = [1,2,3], targetSum = 5
      输出：false
      解释：树中存在两条根节点到叶子节点的路径：
      (1 -> 2): 和为 3
      (1 -> 3): 和为 4
      不存在 sum = 5 的路径。

💻 解题思路

思路1：递归（DFS 自顶向下）

代码实现

from typing import Optional

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        # 更新当前剩余的目标和
        remaining_sum = targetSum - root.val
        
        # 如果是叶子节点，判断剩余目标和是否为 0
        if not root.left and not root.right:
            return remaining_sum == 0
        
        # 递归判断左右子树，只要有一边满足条件即可
        return (self.hasPathSum(root.left, remaining_sum) or 
                self.hasPathSum(root.right, remaining_sum))

📊 性能分析

  • 时间复杂度：O(n)O(n)。其中 nn 为二叉树的节点数，最坏情况下需要遍历所有节点。
  • 空间复杂度：O(h)O(h)。其中 hh 为二叉树的高度，主要为递归调用栈的空间开销。

💡 思考

这道题是二叉树 DFS 的经典入门题。核心在于理解递归的传递性：

  1. 每向下走一层，就将目标和减去当前节点的值。
  2. 当到达叶子节点时，如果剩余目标和刚好为 0，说明从根到当前叶子的路径和正好等于初始的 targetSum。
  3. 使用 or 逻辑运算符可以非常优雅地实现“只要左右子树中有一条路径满足条件即可”的需求。