LeetCode 117. 填充每个节点的下一个右侧节点指针 II
题目描述
题意分析
给普通二叉树的每个节点补上
next指针，使它指向同一层中紧邻右侧的节点；每层最后一个节点的next应为空。树的左右孩子关系保持不变，函数最终返回原来的根节点。同层相邻节点不一定来自同一个父节点，中间也可能隔着多个没有孩子的父节点。本题不保证二叉树是完美的，左右孩子都可能缺失，不能根据固定的父子组合直接决定跨父节点的连接。
所有
next初始都为空，空树也是合法输入。题目的进阶要求使用常数额外空间，因此需要在逐层处理时复用已经建立的指针，而不是保存整层节点的队列。
解法：利用已建立的 next 链逐层连接
核心思路
[!blue]
普通层序遍历会用队列记录同层节点。如果当前层的
next已经从左到右连好，就可以直接沿这条链访问本层，用它替代队列。根节点独占第一层，初始next为空，天然是一条已经建立好的层链，能够作为起点。扫描当前层时，另外构建下一层的链。用
dummy作为不属于原树的哑节点，用tail指向下一层链的最后一个节点。遇到非空左孩子就把它接到尾部，再接非空右孩子；每接入一个孩子，都同步推进tail。哑节点使追加第一个孩子与追加后续孩子使用完全相同的操作。正确顺序来自两点：当前层的父节点按从左到右访问，同一个父节点的孩子按左、右顺序加入。因此下一层所有非空节点也恰好按从左到右的顺序连接。缺少孩子的父节点只需跳过，不影响后来遇到的孩子接到已有链尾，跨父节点连接也自然完成。
本轮沿当前层的
next遍历，只修改下一层孩子的next，不会破坏当前遍历通道。扫描完后，dummy.next就是下一层最左节点，把它交给下一轮；下一层已经完整连好，继续满足相同的不变量。题目保证初始指针为空，下一层最后一个节点不会被接上后继，所以它的
next保持为空。如果当前层没有任何孩子，dummy.next也为空，外层循环结束。每轮重新创建哑节点，避免把上一层的链头带入新一层。
解题步骤
- 令
levelStart = root，表示当前层最左节点；根为空时直接结束。- 每轮创建
dummy，令tail = dummy，准备构建下一层。- 从
levelStart开始沿当前层的next链依次访问父节点。- 非空左孩子先追加到
tail后并更新尾指针，再独立检查右孩子并执行同样操作。- 当前层扫描完成后，令
levelStart = dummy.next，进入刚连接好的下一层。- 新层起点为空时结束，返回原根节点。
代码实现
class Solution {
public Node connect(Node root) {
for (Node levelStart = root; levelStart != null; ) {
// 每层重新记录下一层头尾，当前层只沿已有连接遍历。
Node dummy = new Node(0);
Node tail = dummy;
for (Node node = levelStart; node != null; node = node.next) {
if (node.left != null) {
tail.next = node.left;
tail = tail.next;
}
if (node.right != null) {
tail.next = node.right;
tail = tail.next;
}
}
// 当前层处理完，下一轮从刚生成的链头开始。
levelStart = dummy.next;
}
return root;
}
}
func connect(root *Node) *Node {
for levelStart := root; levelStart != nil; {
// 每层重新记录下一层头尾，当前层只沿已有连接遍历。
dummy := &Node{}
tail := dummy
for node := levelStart; node != nil; node = node.Next {
if node.Left != nil {
tail.Next = node.Left
tail = tail.Next
}
if node.Right != nil {
tail.Next = node.Right
tail = tail.Next
}
}
// 当前层处理完，下一轮从刚生成的链头开始。
levelStart = dummy.Next
}
return root
}
复杂度分析
- 时间复杂度：
O(n)。每个节点在自己所在层被扫描一次，每个孩子最多被接入下一层一次。- 空间复杂度：
O(1)。任意时刻只需当前层起点、遍历指针、下一层头尾及一个哑节点；每层处理完后旧哑节点不再需要，没有队列或递归栈。
关键点总结
[!green]
- 当前层完整的
next链既是上一轮的结果，也是本轮的遍历工具。- 遍历父节点与构建孩子链分属两层，写入不会影响当前层的读取。
- 哑节点与尾指针统一追加操作，不要求相邻父节点拥有固定形态的孩子。
- 初始
next为空保证各层尾节点无需额外清空，最终从没有孩子的一层自然结束。
易错点总结
[!yellow]
- 左右孩子写成
if / else：左右孩子可能同时存在，必须分别判断，否则会漏掉一个。- 先连右孩子再连左孩子：会颠倒同一个父节点的孩子顺序，破坏层内从左到右的要求。
- 追加后不移动
tail：下一次追加会覆盖刚建立的连接，丢失已经接入的节点。- 每轮沿用旧的下一层链头：当前层没有孩子时仍可能回到旧链，必须重新初始化哑节点和尾指针。
- 用
levelStart.next进入下一层：它仍位于当前层，真正的下一层起点是dummy.next。- 直接连接到右邻父节点的左孩子：右邻父节点可能没有左孩子甚至没有孩子，应该统一按顺序追加所有非空孩子。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 116. 填充每个节点的下一个右侧节点指针 | 中等 | 去掉完美二叉树前提后，不能假设相邻父节点都有孩子，常用下一层哑节点串接。 |
| 102. 二叉树的层序遍历 | 中等 | 同层相邻关系来自BFS顺序，next链可替代显式队列遍历每层。 |