对应着lintcode376题。
给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径,指的是从根节点到叶节点的路径。
样例 样例1:
输入: {1,2,4,2,3} 5 输出: [[1, 2, 2],[1, 4]] 说明: 这棵树如下图所示: 1 / \ 2 4 / \ 2 3 对于目标总和为5,很显然1 + 2 + 2 = 1 + 4 = 5 样例2:
输入: {1,2,4,2,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,root,target)
return res
def pathSum(self,res,tmp,root,target):
if root == None:
return
#首先将当前节点的值加入到tmp中
tmp.append(root.val)
#如果当前节点没有左右孩子,说明是叶子节点
if root.left == None and root.right == None:
#计算根节点到叶子节点的值
s = sum(tmp)
#如果该值等于target
if s == target:
#这里需要拷贝一份tmp,再加入到结果中
newtmp=tmp[:]
res.append(newtmp)
#如果有左孩子
if root.left!=None:
self.pathSum(res,tmp,root.left,target)
#如果遍历到叶子节点了,且不符合sum(tmp)==target,则最后面的节点出栈
tmp.pop()
#如果有右孩子
if root.right!=None:
self.pathSum(res,tmp,root.right,target)
#如果遍历到叶子节点了,且不符合sum(tmp)==target,则最后面的节点出栈
tmp.pop()