北京网站建设公司,怎么做王者荣耀网站,网站权重什么意思,菜单设计制作模板免费Problem: 面试题 04.03. 特定深度节点链表 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
根据题意需要取出二叉树每一层节点组成的链表并将其添加到一个数组中。我们将该要求分解成如下的操作#xff1a; 1.利用BFS获取二叉树每一层的节点 2.利用链表的尾插法将二… Problem: 面试题 04.03. 特定深度节点链表 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
根据题意需要取出二叉树每一层节点组成的链表并将其添加到一个数组中。我们将该要求分解成如下的操作 1.利用BFS获取二叉树每一层的节点 2.利用链表的尾插法将二叉树每一层的节点添加到该层节点组成的链表中采用虚拟头节点和尾指针 解题方法 1.创建ArrayList集合便于存贮每一层节点组成的链表 2.利用BFS算法获取二叉树每一层的节点在该遍历每一层时先创建虚拟头节点和尾指针尾指针初始化指向创建的虚拟头节点利用尾插法将该层的节点添加到该层的链表中最后再将虚拟头节的下一个节点添加到ArrayList集合中 3.将ArrayList集合转换为数组并返回 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) Code
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {/*** Gets a list of nodes at each level of a tree** param tree the root node of a tree* return ListNode[]*/public ListNode[] listOfDepth(TreeNode tree) {if (tree null) {return new ListNode[0];}ListListNode result new ArrayListListNode();QueueTreeNode queue new LinkedListTreeNode();//Add the root node to queuequeue.add(tree);//BFSwhile (!queue.isEmpty()) {//Create a dummy node and a tail pointerListNode dummyHead new ListNode(Integer.MAX_VALUE);ListNode tail dummyHead;int curLevelNum queue.size();for (int i 0; i curLevelNum; i) {TreeNode curLevelNode queue.poll();//Adds the nodes of the current layer//to the resulting linked listtail.next new ListNode(curLevelNode.val);tail tail.next;if (curLevelNode.left ! null) {queue.add(curLevelNode.left);}if (curLevelNode.right ! null) {queue.add(curLevelNode.right);}}//Add the LinkedList of the current level//to the resulting listresult.add(dummyHead.next);}ListNode[] finalResult new ListNode[result.size()];//Convert List to an array of intfor (int i 0; i result.size(); i) {finalResult[i] result.get(i);}return finalResult;}
}
