路径总和

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#112

📖 题目

判断二叉树中是否存在一条从根到叶子的路径，路径上所有节点值加起来正好等于 targetSum。

🆕 新知识

is 比较的是身份（是不是同一个对象），== 比较的是值。判断 None 要用 is None，不是 == None——这是 Python 的约定写法。

💡 思路

递归时带着"还差多少凑够目标值"往下传：每经过一个节点就减去它的值，走到叶子节点检查剩余值是否正好归零。

关键陷阱：空节点不等于叶子节点。叶子节点是"存在但没有子节点"的节点，空节点是 None，根本不存在。如果把空节点当成路径终点来判断，遇到只有一侧子树的树会误判——路径可能在半路的空节点上被错误地判定为"到达终点"，但那根本不是一条真实的根到叶子路径。

💻 代码

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        if root.left is None and root.right is None:   # 真正的叶子
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or \
               self.hasPathSum(root.right, targetSum - root.val)

时间复杂度 O(n)，空间复杂度 O(h)，h 是树高。