对应着lintcode376题。
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
样例
样例1:
输入:
{1,2,4,3}
5
输出: [[1,2],[1,4]]
说明:
这棵树如下图所示：
1
/ \
2 4
/ \
2 3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
样例2:
输入:
{1,3}
3
输出: []
说明:
这棵树如下图所示：
1
/ \
2 4
/ \
2 3
注意到题目要求我们寻找从根节点到叶子节点的路径。
1 + 2 + 2 = 5,1 + 2 + 3 = 6,1 + 4 = 5
这里没有合法的路径满足和等于3.
""" Definition of TreeNode: class TreeNode: def __init__(self,val): self.val = val self.left,self.right = None,None """ class Solution: @param: root: the root of binary tree @param: target: An integer @return: all valid paths """ def binaryTreePathSum(self,root,target): # write your code here global res 保存结果 res=[] 临时数组 tmp=[] self.pathSum(res,tmp,target) return res pathSum(self,res,1)">if root == None: return 首先将当前节点的值加入到tmp中 tmp.append(root.val) 如果当前节点没有左右孩子，说明是叶子节点 if root.left == None and root.right ==计算根节点到叶子节点的值 s = sum(tmp) 如果该值等于target if s == target: 这里需要拷贝一份tmp，再加入到结果中 newtmp=tmp[:] res.append(newtmp) 如果有左孩子 if root.left!=None: self.pathSum(res,root.left,target) 如果遍历到叶子节点了，且不符合sum(tmp)==target，则最后面的节点出栈 tmp.pop() 如果有右孩子 if root.right!= tmp.pop()