LeetCode 面试题 04.03. 特定深度节点链表

一、题目

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

  点击此处跳转题目。

示例：

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

      1
     / \ 
    2   3
   / \   \ 
  4   5   7
 /
8
1
2
3
4
5
6
7

输出：[[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) {
        List<ListNode> lst = new List<ListNode>();  // 存放返回结果
        List<TreeNode> temp = new List<TreeNode>(); // 存放每一深度的树结点
        Queue<TreeNode> q = new Queue<TreeNode>();  // 队列
        q.Enqueue(tree);                            // 压入头结点
        do {
            // 遍历每一层，将其全部压入 q
            while (q.Count != 0) {
                TreeNode tn = q.Dequeue();
                if (tn == null) continue; // 不处理 null
                temp.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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(m)$，$m$ 为一层中最多的节点个数，即 $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) {
        List<ListNode> lst = new List<ListNode>();  // 存放返回结果
        Queue<TreeNode> q = new Queue<TreeNode>();  // 队列
        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，重新指向 head
                p.next = null;                             // 清除上个链表
            }

            # endregion
        } while (num != 0);
        return lst.ToArray();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

• 时间复杂度：$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) {
        List<ListNode> lst = new List<ListNode>(); // 存放返回结果
        List<ListNode> ln = new List<ListNode>();  // 存放每一层最后一个结点
        Partition(lst, tree, ln, 0);
        return lst.ToArray();
    }

    public void Partition(List<ListNode> lst, TreeNode tn, List<ListNode> 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); // 右孩子来一次
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(h)$，$h$ 为树的高度，即 $O(\log n)$。