网站建设基本流程价格,网站设计制作的服务好不好,泉州网站排名,网站开发的报告书文章目录 一、题目二、C# 题解1. 队列层序遍历#xff08;2 层 while#xff09;2. 队列层序遍历#xff08;1 层 while#xff09;3. 递归解法 一、题目 给定一棵二叉树#xff0c;设计一个算法#xff0c;创建含有某一深度上所有节点的链表#xff08;比如#xff0c… 文章目录 一、题目二、C# 题解1. 队列层序遍历2 层 while2. 队列层序遍历1 层 while3. 递归解法 一、题目 给定一棵二叉树设计一个算法创建含有某一深度上所有节点的链表比如若一棵树的深度为 D则会创建出 D 个链表。返回一个包含所有深度的链表的数组。 点击此处跳转题目。
示例 输入[1,2,3,4,5,null,7,8] 1/ \ 2 3/ \ \ 4 5 7/
8输出[[1],[2,3],[4,5,7],[8]] 二、C# 题解
1. 队列层序遍历2 层 while 使用队列存放每一层结果处理时一层一层处理需额外使用一个数组记录每一层内容
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val x; }* }*/
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public ListNode[] ListOfDepth(TreeNode tree) {ListListNode lst new ListListNode(); // 存放返回结果ListTreeNode temp new ListTreeNode(); // 存放每一深度的树结点QueueTreeNode q new QueueTreeNode(); // 队列q.Enqueue(tree); // 压入头结点do {// 遍历每一层将其全部压入 qwhile (q.Count ! 0) {TreeNode tn q.Dequeue();if (tn null) continue; // 不处理 nulltemp.Add(tn);}// 带有头结点的链表使得后续操作统一ListNode ln new ListNode(0), head ln;for (int i 0; i temp.Count; i) {ln.next new ListNode(temp[i].val);ln ln.next; // ln 始终指向尾结点// 压入左右孩子q.Enqueue(temp[i].left);q.Enqueue(temp[i].right);}if (head.next ! null) lst.Add(head.next); // 链表不为空存放结果temp.Clear(); // 清楚该层进入下一层} while (q.Count ! 0);return lst.ToArray();}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( m ) O(m) O(m) m m m 为一层中最多的节点个数即 O ( n ) O(n) O(n)。
2. 队列层序遍历1 层 while 看了一下部分大佬的题解受到启发使用 num 记录每层结点个数可以节省一个数组的空间。只需添加一个头结点 head用于记录每层链表指针 p 指向链表尾结点方便添加结点。代码方面也只需用一个 while显得高大上hh
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val x; }* }*/
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public ListNode[] ListOfDepth(TreeNode tree) {ListListNode lst new ListListNode(); // 存放返回结果QueueTreeNode q new QueueTreeNode(); // 队列ListNode head new ListNode(0), p head; // head 为头结点后续存放每层链表p 指向尾结点q.Enqueue(tree); // 压入头结点int num 1; // num 记录 q 中元素个数do {# region 逐层处理TreeNode tn q.Dequeue(); // 弹出元素 tn// tn 为 null 则跳过该阶段if (tn ! null) {p.next new ListNode(tn.val); // 添加新结点p p.next; // 移动尾指针q.Enqueue(tn.left); // 左孩子进队列q.Enqueue(tn.right); // 右孩子进队列}num--; // 处理完元素更新 num# endregion# region 每层处理完后进入下一层的准备工作if (num 0) { // num 为 0表示处理完一层num q.Count; // 更新 num 为下一层的数量if (head.next ! null) lst.Add(head.next); // 若该层的链表不为空则添加到结果中p head; // 更新 p重新指向 headp.next null; // 清除上个链表}# endregion} while (num ! 0);return lst.ToArray();}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度同上 O ( n ) O(n) O(n)。
3. 递归解法 也可以使用递归但是需要用数组记录每层最后一个结点。当遍历到某个结点时识别该结点对应哪层之后添加进该层的链表中具体实现如下
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val x; }* }*/
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public ListNode[] ListOfDepth(TreeNode tree) {ListListNode lst new ListListNode(); // 存放返回结果ListListNode ln new ListListNode(); // 存放每一层最后一个结点Partition(lst, tree, ln, 0);return lst.ToArray();}public void Partition(ListListNode lst, TreeNode tn, ListListNode ln, int deep) {if (tn null) return;ListNode node new ListNode(tn.val);if (lst.Count deep) { // 到达新层则动态添加数组长度lst.Add(node);ln.Add(node);}else { // 若已到达该层更新 ln 并将 node 添加进该层链表ln[deep].next node;ln[deep] node;}Partition(lst, tn.left, ln, deep 1); // 左孩子来一次Partition(lst, tn.right, ln, deep 1); // 右孩子来一次}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( h ) O(h) O(h) h h h 为树的高度即 O ( log n ) O(\log n) O(logn)。
