前序遍历 + 回溯
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findPath(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
self.res=[]
def dfs(root,path,target):
if root.left==None and root.right==None and target==root.val:
path.append(root.val)
self.res.append(path)
return
if root.left :dfs(root.left,path+[root.val],target-root.val)
if root.right :dfs(root.right,path+[root.val],target-root.val)
if root==None:return []
dfs(root,[],sum)
return self.res