特定深度节点链表

题目取自《程序员面试金典》4.3

思路

类似广度优先遍历，通过遍历每一层，并逐层添加相应节点

错误来源

没有正确的处理链表头节点的位置，因为力扣题目里没有直接使用LinkedList类，而是使用了最基本的节点，所以需要使用一个指针对头节点进行保存，另一个指针进行添加操作。

错误示范

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode[] addLists(ListNode[] listOfLevel, int index, TreeNode tree)
{
        if (tree == null) return listOfLevel;
        ListNode temp = listOfLevel[index];
        while (temp!= null)
        {
            temp = temp.next;
        }
        temp = new ListNode(tree.val);
        temp = temp.next;
            
        return listOfLevel;
}

正确答案

先通过c#，list类对每一层进行节点的创建，设置计数器对每一层的节点数量进行控制，最后再创建答案的数组。

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
public ListNode[] ListOfDepth(TreeNode tree)
{
    if (tree == null) return null;
    List<ListNode> listOfLevels = new List<ListNode>();
    int curr = 1;
    int next = 0;
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(tree);
    ListNode node = new ListNode(0);
    ListNode find = node;
    while (queue.Count > 0)
    {
        TreeNode temp = queue.Dequeue();
        node.next = new ListNode(temp.val);
        node = node.next;
        curr--;
        if (temp.left != null)
        {
            queue.Enqueue(temp.left);
            next++;
        }
        if (temp.right != null)
        {
            queue.Enqueue(temp.right);
            next++;
        }
        if(curr == 0)
        {
            curr = next;
            next = 0;
            listOfLevels.Add(find.next);
            node = new ListNode(0);
            find = node;
        }
    }


    return listOfLevels.ToArray();
}