112_路径总和

类型：树

• 112. 路径总和 💚

  https://leetcode-cn.com/problems/path-sum/

  ❓ 判断树中是否存在 根节点到叶子节点 的路径，路径上节点值相加等于目标和 targetSum。

  💡 递归

  假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。

  class Solution:
      def hasPathSum(self, root: TreeNode, sum: int) -> bool:
          if not root:
              return False
          if not root.left and not root.right:
              return sum == root.val
          return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

  时间复杂度：O(n)。空间复杂度：O(h)，h 指树的高度。