LeetCode 面试题 04.03. 特定深度节点链表
题目描述
题意分析
将二叉树中相同深度的节点值放入同一条链表，返回从根层到最深层的链表头数组。链表节点需要新建，原二叉树保持不变；空树没有任何层，对应空结果。
解法：按层 BFS 并尾接新链表
核心思路
[!blue]
题目要求按深度分组，广度优先搜索正好逐层访问节点。每轮开始时，队列中都是当前层的节点，先保存此时的队列大小
k，本轮只出队这k个节点。出队一个节点后，把它的非空左、右孩子依次加入队尾。虽然队列中逐渐混入下一层节点，但处理次数已经固定，它们不会被本轮取出。当前层处理完后，队列中恰好只剩下一层，从而保持分层顺序；先加入左孩子也使每层按从左到右连接。
每层新建一个哑节点
dummy，用cur指向当前链尾。访问树节点时，新建对应的链表节点，接到cur.next后再移动尾指针。这样首节点和后续节点使用同一套追加逻辑，本层完成后保存dummy.next，不把哑节点算进结果。队列为空就表示全部层都已处理。每个树节点恰好出队一次，也只创建一个对应的结果节点，因此不会遗漏或重复。
解题步骤
- 空树直接返回空结果。
- 根入队，每轮新建哑节点及链表尾指针。
- 固定本层节点数，出队时尾接链表节点，非空孩子入队。
- 本层结束保存 dummy.next，再处理下一层。
每一层都重新创建哑节点和尾指针，链表之间才不会连在一起。只有根节点时，第一轮直接生成一条长度为 1 的链表。
代码实现
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
if (tree == null) {
return new ListNode[0];
}
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) {
if tree == nil {
return
}
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)$，每个树节点入队、出队并生成一个链表节点。
- 空间复杂度：辅助队列为 $O(w)$，
w是最大层宽；输出链表及头数组另占 $O(n)$。
关键点总结
[!green]
固定层大小负责划分深度，哑节点和尾指针负责构造本层链表；遍历队列与输出链表各自承担一个职责。
易错点总结
[!yellow]
- 不要用不断变化的队列长度作本层终止条件。
- 每层重建哑节点，避免把两层接到一起。
- 输出是新链表节点，不能直接复用树节点结构。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 层序分层完全相同，本题把每层的输出容器改为单链表。 |
| 116. 填充每个节点的下一个右侧节点指针 | 中等 | 同样按层连接节点，原题连接已有树节点的 next，本题生成独立链表。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！