经典面试题(三十六)-- 特定深度节点链表

发布于 2021-09-07 11:07 ，所属分类：2021面试经验技巧分享

来源：LeetCode

难度：中等

描述：

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


示例1：

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


分析：

本题是给我们一棵二叉树，让咱们将树的每层中的节点串连起来形成链表，然后返回所有层级的链表数组。

其实归根结底考察的还是二叉树的层序遍历和链表的构建，具体解法如下


解题


方法一：广度优先遍历

思路：

采用广度优先遍历的方式对二叉树进行层层遍历

利用队列存储二叉树每层的节点。队列的size就是当前层二叉树节点个数，因此每次循环只需将前size个节点出队即可完成本层元素的遍历。

队头就是每层最左边的节点，因此每次循环根据队头构建链表头节点，同时将队头元素的左右节点入队，并且根据1~size个元素构建链表剩余节点


代码：

 1publicListNode[]listOfDepth(TreeNodetree){
 2if(tree==null){
 3returnnull;
 4}
 5//结果数组
 6List<ListNode>ans=newArrayList<>();
 7//广度队列
 8Queue<TreeNode>queue=newLinkedBlockingQueue<>();
 9queue.add(tree);
10
11while(!queue.isEmpty()){
12intsize=queue.size();
13//先根据队首构造链表头结点
14ListNodehead=newListNode(queue.peek().val);
15//根节点如数组
16ans.add(head);
17ListNodetemp=head;
18for(inti=0;i<size;i++){
19TreeNoderoot=queue.poll();
20if(i!=0){
21//剩余队列元素构建链表其余节点
22temp.next=newListNode(root.val);
23temp=temp.next;
24}
25//左右子节点入队
26if(root.left!=null){
27queue.add(root.left);
28}
29if(root.right!=null){
30queue.add(root.right);
31}
32}
33}
34
35returnans.toArray(newListNode[0]);
36}


时间复杂度：O(n) n为节点个数

空间复杂度：O(n)



以上仅是个人思路解法，觉得还不错欢迎点赞分享


往期精彩推荐

  • 二叉树(十一)--二叉树展开为链表

  • 十大经典排序(九)--桶排序

  • 数组篇(五) -- 路径总和 II


点击下方链接，gongzhong号，更多精彩等你发现


相关资源