Leetcode112-路径总和-Python实现

• 题目要求：

• 思路：

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

# 如果root为空，说明yaoif not root:    return Falseif 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，结果就为Truereturn left or right

• 完整代码：

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass 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