题目描述
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
解题思路：
递归，首先从根节点进行递归，然后再从子节点进行递归，判断路径上是否出现和为目标值的路径。
class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def __init__(self): self.result = [] def pathSum(self, root, sum): if not root: return 0 def Search(node, sum, tempSum, tempList): if node is None: return tempSum += node.val if tempSum == sum: tempList.append(node.val) self.result.append(tempList) Search(node.left, sum, tempSum, tempList + [node.val]) Search(node.right, sum, tempSum, tempList + [node.val]) Search(root, sum, 0, []) self.pathSum(root.left, sum) self.pathSum(root.right, sum) return self.result n10 = TreeNode(10) n5 = TreeNode(5); n_3 = TreeNode(-3) n3 = TreeNode(3); n2 = TreeNode(2); n11 = TreeNode(11) n9 = TreeNode(3); n_2 = TreeNode(-2); n1 = TreeNode(1) n10.left = n5; n10.right = n_3 n5.left = n3; n5.right = n2; n_3.right = n11 n3.left = n9; n3.right = n_2; n2.right = n1 S = Solution() print(S.pathSum(n10, 8))
