题解 | #二叉树中和为某一值的路径(二)#

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, target):
        # write code here
        self.target = target
        self.res = []
        self.parent = {} # node: parent node
        
        def getPath(node):
            path = [node.val]
            while node in self.parent:
                path = [self.parent[node].val] + path
                node = self.parent[node]
            return path
        
        if not root:
            return []
        queue = [root]
        while queue:
            node = queue.pop(0)
            if not node.left and not node.right:
                if sum(getPath(node)) == self.target:
                    self.res.append(getPath(node))
            if node.left:
                self.parent[node.left] = node
                queue.append(node.left)
            if node.right:
                self.parent[node.right] = node
                queue.append(node.right)
        return self.res