437 path sum iii
437. Path Sum III
题目: https://leetcode.com/problems/path-sum-iii/
难度: Easy
思路：
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if not root:
return 0
res = self.auxPathSum(root, sum)
res += self.pathSum(root.left, sum)
res += self.pathSum(root.right, sum)
return res
def auxPathSum(self, root, sum):
if not root:
return 0
if sum == root.val:
# 因为可能有负值, 所以sum为0也会有解, 必须加上
return 1 + self.auxPathSum(root.left, 0) + self.auxPathSum(root.right, 0)
else:
return self.auxPathSum(root.left, sum - root.val) + self.auxPathSum(root.right, sum - root.val)
