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

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

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


        
        
        
        
        
        
        
        
        
        




        
        
        
        
        
        
        
        
        
        

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
简历当中有水分算不算造假...
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务