112. 路径总和
https://leetcode-cn.com/problems/path-sum/
解法一:dfs递归
递归左右子树,每次减去当前节点值
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: #空节点
return True if sum == 0 else False #sum为0才正确,大于或小于0都不正确
if sum < 0:
return False
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
但是这种写法对于root为空且sum为0的case无法通过,因此改变判断时机,在叶节点而不是空节点才判断sum是否为0
而且sum<0就判否也不对,因为节点值可能为负
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 == 0
#对左右子树递归
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
最后更新于