二叉树中和为某一值的路径

image.png

用回溯法！！！
前序优先遍历（dfs）, 判断是否满足条件，满足就累计一个答案，然后深度遍历，别忘了最后回溯，要删掉路径中的节点

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    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]