给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
思路：
主要的点在于不确定当前的节点是否存在于一条路径上，该路径的和为sum，所以需要分情况讨论
① 假设当前节点在一条这样的路径上，则递归寻找其左右子树，使剩下的和为sum - root.val
② 假设当前节点并不在这样一条路径上，则递归寻找其左右子树，使剩下的和为sum
③注意返回值条件
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def pathSum(self, root: TreeNode, sum: int) -> int: if root == None: return 0 res = 0 res = res + self.findPath(root, sum) # 不包含当前root节点的路径，和为sum的路径个数 res = res + self.pathSum(root.left, sum) res = res + self.pathSum(root.right, sum) return res def findPath(self, root: TreeNode, sum: int) -> int: # 返回包含root节点的路径，和为sum的路径个数 if root == None: return 0 res = 0 if root.val == sum: res = res + 1 res = res + self.findPath(root.left, sum - root.val) res = res + self.findPath(root.right, sum - root.val) return res
