题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
python BFS:
# -*- 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
