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

2026-03-28 HGNULB 约 8 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

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

题意分析

给一棵二叉树，把每一层的所有节点串成一条单链表，最后返回一个链表数组，数组下标即深度：第 0 个链表是根这一层，第 1 个是根的孩子这一层，依此类推。

「每一层单独成表」这句话给出了两个硬要求：一是必须知道每个节点属于第几层，二是同一层内部的先后顺序必须与从左到右一致。这两条合起来意味着遍历必须按层推进，且每层要有明确的起止边界——只知道节点顺序不知道层的分界线，是无法切出多条链表的。

输出是链表而不是值数组，说明每处理一个节点都要新建链表节点并接到当前层的尾部；「往尾部追加」这个动作本身就提示了需要一个尾指针，否则每次都要从头走一遍，单层就退化成平方级。

边界：树的层数至少为 1，最后一层可能只有一个节点；某个节点可能只有左孩子或只有右孩子，入队前要各自判空；返回的数组长度等于树高，不能多出一条空链表。

解法：广度优先搜索

核心思路

先想深度优先：递归时带上深度参数 d，把节点值追加到 answer[d] 对应的链表尾。这条路能通，但要额外维护每条链表的尾指针数组，还要处理 answer 何时扩容，代码分支明显多于按层推进；更重要的是它把「层」这个概念藏在了参数里，而不是显式地摆在结构上。

换成按层推进：队列里始终只放同一批待处理的节点，处理它们时把下一层的孩子追加到队尾。这里的关键观察是——进入每轮循环时，队列里恰好是完整的一层。只要在轮次开始时先把队列长度 k 记下来，然后严格只弹 k 次，本轮处理的就是且仅是这一层，哪怕循环体内不断往队尾追加孩子也不会串层。

这条「先量长度再定量弹出」的性质就是本题的核心不变量：k = q.size() 在弹出前取值，之后的入队只影响下一轮。它把「层的分界线」从额外的标记变量变成了一个循环上界，这也是层序遍历模板中最值得记住的一行。

每层内部再维护一条链表：用哑节点 dummy 作表头、cur 作尾指针，每弹出一个节点就 cur.next = new ListNode(值) 并推进 cur。哑节点的作用是让「接第一个节点」和「接后续节点」写成同一行，省掉一次空判分支；本轮结束后 dummy.next 就是这一层的真实表头。

解题步骤

初始化：结果用可变列表 answer 收集，队列里先放入根节点。用列表而不是定长数组，是因为树高事先未知。

外层循环按层推进：条件是队列非空。队列空意味着上一轮没有产生任何孩子，也就走到了最后一层之后。

每层开头建哑节点：dummy 与尾指针 cur 都必须在层内循环之外、外层循环之内创建——放到外面会让所有层串成一条，放到内层则每个节点都自成一表。

锁定本层长度：for (int k = q.size(); k > 0; --k)。q.size() 只在循环初始化时求值一次，这是层不串位的根本保证；写成 for (int i = 0; i < q.size(); ++i) 就会因为每轮重新求值而把后续层一起吞进来。

弹节点、接链表、压孩子：弹出队首后先建链表节点接到 cur 后面并推进尾指针，再把非空的左右孩子入队。左先右后的顺序决定了下一层的从左到右次序，不能颠倒。

收尾：本层循环结束后把 dummy.next 加入 answer，然后进入下一轮；全部结束后把列表转成数组返回。

以 tree = [1, 2, 3, null, 4] 走一遍，即根为 1，左右孩子分别是 2 和 3，节点 2 只有右孩子 4。

第一轮：队列是 [1]，k = 1。弹出 1，链表接成 1；1 的左右孩子 2、3 依次入队。本轮结束，answer 得到第一条链表 1，队列变为 [2, 3]。

第二轮：k 在弹出前取值为 2，所以本轮只弹两次，尽管循环中途会往队尾追加 4。弹出 2，链表接成 2，2 的右孩子 4 入队（左孩子为空跳过）；弹出 3，链表接成 2 → 3，3 无孩子。本轮结束，answer 得到第二条链表 2 → 3，队列变为 [4]。

第三轮：k = 1，弹出 4，链表为 4，无孩子入队。answer 得到第三条链表 4，队列变空，外层循环退出。最终返回三条链表：1、2 → 3、4。若第二轮把 k 写成每次重新取 q.size()，追加进来的 4 会被同一轮吞掉，第二层错误地变成 2 → 3 → 4，而第三层凭空消失。

代码实现

class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        List<ListNode> answer = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(tree);

        while (!q.isEmpty()) {
            // 哑节点让「接首个节点」和「接后续节点」写法一致。
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;

            // k 在弹出前锁定，本轮只处理当前这一层。
            for (int k = q.size(); k > 0; --k) {
                TreeNode node = q.poll();
                cur.next = new ListNode(node.val);
                cur = cur.next;
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }

            answer.add(dummy.next);
        }

        return answer.toArray(new ListNode[0]);
    }
}

func listOfDepth(tree *TreeNode) (answer []*ListNode) {
    q := []*TreeNode{tree}

    for len(q) > 0 {
        // 哑节点让「接首个节点」和「接后续节点」写法一致。
        dummy := &ListNode{}
        cur := dummy

        // k 在弹出前锁定，本轮只处理当前这一层。
        for k := len(q); k > 0; k-- {
            node := q[0]
            q = q[1:]
            cur.Next = &ListNode{Val: node.Val}
            cur = cur.Next
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }

        answer = append(answer, dummy.Next)
    }

    return
}

复杂度分析

时间复杂度：$O(n)$，n 为节点数。每个节点恰好入队一次、出队一次，出队时只做常数次链表接续与孩子判空。

空间复杂度：$O(n)$，队列在最宽一层最多存下该层全部节点，完全二叉树时约为 n / 2；输出的链表本身也占 $O(n)$，但那是必需的结果空间。

关键点总结

层序遍历的分界线靠「弹出前锁定 k = q.size()」实现，而不是靠额外的层标记节点；这一行是整个模板的骨架，写对了 102、103、199 等一整类题都能套用。

建链表时用哑节点起头，可以把首节点特判消掉；面试里主动说一句「哑节点是为了统一空表与非空表的接法」，比默默写出来更能体现设计意识。

尾指针 cur 必须随着接续同步推进，否则每次都从表头接，等于反复覆盖；链表构造题里「头指针留着返回、尾指针负责推进」是固定分工。

左孩子先入队、右孩子后入队，直接决定了下一层的左右次序；顺序类需求要落到入队顺序上，而不是事后排序。

面试官常追问能否用深度优先做：可以，递归带深度参数并为每层维护尾指针即可，但代码更绕；能说清两种写法的取舍，比只会一种更占优势。

易错点总结

循环条件写成 for (int i = 0; i < q.size(); ++i)：[1, 2, 3, null, 4] → 处理第二层时 4 被追加进队列并在同一轮被吞掉，输出变成两层 1 与 2 → 3 → 4，第三层丢失。

哑节点建在外层循环之外：[1, 2, 3] → 所有层共用一条链表，answer 里三项全是 1 → 2 → 3 的不同后缀，层结构彻底消失。

哑节点建在内层循环之内：[1, 2, 3] → 第二层的每个节点各成一表，answer 只收到最后一个节点，得到 3 而不是 2 → 3。

忘记推进尾指针：[1, 2, 3] → 第二层里 cur.next 被 2 和 3 先后覆盖，最终链表只剩 3。

入队前不判空：[1, 2, 3, null, 4] → 节点 2 的空左孩子被压入队列，下一轮弹出后访问 node.val 直接空指针。

左右孩子入队顺序颠倒：[1, 2, 3] → 第二层输出 3 → 2，值都在但顺序与「从左到右」相反。

本层结束时把 dummy 而不是 dummy.next 存进结果：[1] → 每条链表都多出一个值为 0 的表头，输出变成 0 → 1。

对空树不做保护就直接入队：tree = null → 队列里压进空指针，第一轮弹出后访问 node.val 崩溃；本题保证树非空才敢这么写，换到 102 题必须先判空返回空结果。

用 answer.toArray(new ListNode[0]) 之外的写法拼数组时长度算错：预先按估计的树高开定长数组，[1, 2, 3, null, 4] 这类不满的树会在末尾留下空位，判题读到 null 项直接失败。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	同一套按层模板，只是每层收成列表而非链表，是本题的原型
107. 二叉树的层序遍历 II	中等	层序照旧，收尾时整体反转或头插，考的是结果组装顺序
103. 二叉树的锯齿形层序遍历	中等	需按层号交替方向，用双端队列头插尾插比事后反转更省一次遍历
199. 二叉树的右视图	中等	每层只取最后一个节点，考的是层内下标与层边界的对应
515. 在每个树行中找最大值	中等	层内做聚合而非收集，把链表换成一个滚动的最大值变量
637. 二叉树的层平均值	简单	层内求和再除以 `k`，注意用长整型累加避免溢出
662. 二叉树最大宽度	中等	队列里要额外携带完全二叉树编号，宽度由本层首尾编号差得出
429. N 叉树的层序遍历	中等	孩子从固定两个变成一个列表，入队改为遍历 `children`
958. 二叉树的完全性检验	中等	空节点也要入队，靠「首个空之后不得再出现非空」判定完全性
剑指 Offer 32 - II. 从上到下打印二叉树 II	简单	与 102 同题，可直接套用本题的层边界写法