image.png

用回溯法！??！
前序優(yōu)先遍歷（dfs）, 判斷是否滿足條件，滿足就累計一個答案，然后深度遍歷，別忘了最后回溯，要刪掉路徑中的節(jié)點

代碼：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二維列表，內(nèi)部每個列表表示找到的路徑
    def FindPath(self, root, expectNumber):
        # write code here
        if root == None:
            return []
        self.ans = []
        path = []
        currentSum = 0
        self.findPath(root, expectNumber, path, currentSum)
        return self.ans
    def findPath(self, root, expectNumber, path, currentSum):
        #if root == None:
            #return
        currentSum += root.val
        path.append(root.val)
        isleaf = (root.left == None and root.right == None)
        if currentSum == expectNumber and isleaf:
            tmp = []
            if path:
                tmp = path[:]
            self.ans.append(tmp)
        if root.left:
            self.findPath(root.left, expectNumber, path, currentSum)
        if root.right :
            self.findPath(root.right, expectNumber, path, currentSum)
        del path[-1]