问题给定一棵二叉树，设计一个算法，创建一个包含一定深度所有节点的链表（例如，如果一棵树的深度为D，则D个链表为创建）。返回包含所有深度的链表的数组。示例：输入：[1,2,3,4,5,null,7,8]1/\23/\\457/8输出：[[1],[2,3],[4,5,7],[8]]思想BFS层次遍历，每一层节点构成一个单向链表。代码Python3#二叉树节点的定义。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=None#单链表的定义。#classListNode:#def__init__(self,x):#self.val=x#self.next=Noneclass解决方案：deflistOfDepth(self,tree:TreeNode)->List[ListNode]:importcollectionsifnottree:return[]queue=collections.deque()queue.append(tree)res=[]#BFSwhilequeue:n=len(queue)foriinrange(n):node=queue.popleft()ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)#当前层的第一个节点ifi==0:#头节点head=ListNode(node.val)tmp=headelse:tmp.next=ListNode(node.val)tmp=tmp.next#这里添加res为headres.append(head)returnreslinkGitHub
