LeetCode | 面试题 04.03. 特定深度节点链表【Python】

概述问题力扣给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为D，则会创建出D个链表）。返回一个包含所有深度的链表的数组。示例：输入：[1,2,3,4,5,null,7,8]1/\23/\\457/8输出：[[1 问题

力扣

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：

输入：[1,2,3,4,5,null,7,8]        1       /  \       2    3     / \    \     4   5    7   /  8输出：[[1],[2,3],[4,5,7],[8]]

思路

BFS

层次遍历，每层节点单独构成一个单链表。

代码python3

# DeFinition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None# DeFinition for singly-linked List.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def listofDepth(self, tree: TreeNode) -> List[ListNode]:        import collections        if not tree:            return []                queue = collections.deque()        queue.append(tree)        res = []        # BFS        while queue:            n = len(queue)            for i in range(n):                node = queue.popleft()                if node.left:                    queue.append(node.left)                if node.right:                    queue.append(node.right)                # 当前层的第一个节点                if i == 0:                    # 头节点                    head = ListNode(node.val)                    tmp = head                else:                    tmp.next = ListNode(node.val)                    tmp = tmp.next            # 这里加入res的是head            res.append(head)        return res

链接

GitHub

总结

以上是内存溢出为你收集整理的LeetCode | 面试题 04.03. 特定深度节点链表【Python】全部内容，希望文章能够帮你解决LeetCode | 面试题 04.03. 特定深度节点链表【Python】所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。