Leetcode112-路径总和-Python实现

• 题目要求：

• 思路：

  • 递归
  • 把（sum – 当前节点的 val）传给当前节点的左子树和右子树
  • 如果当前节点没有左子树，也没有右子树，而且 sum 为 0，说明到达了一个叶子节点，而且到达这个叶子节点的路径中，有一条路径，这条路径上的所有节点值相加等于 sum，返回 True
• 核心代码：

# 如果 root 为空，说明 yao
if not root:
    return False
if root.val == sum and not root.left and not root.right:
    return True
# 递归
left = self.hasPathSum(root.left, sum - root.val)
right = self.hasPathSum(root.right, sum - root.val)
# left 和 right 有一个为 True，结果就为 True
return left or right

• 完整代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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