LeetCode 116. 填充每个节点的下一个右侧节点指针

2024-10-23 HGNULB 约 9 分钟

文章信息 9 个分类 6 个标签

分类

题目描述

✅ 116. 填充每个节点的下一个右侧节点指针

题意分析

给一棵每个节点带 next 字段的二叉树，要把同一层的节点按从左到右的顺序用 next 串成一条链，每层最右边那个节点的 next 置空，最后返回根。

最重要的约束信号是「完美二叉树」：所有非叶节点都同时拥有左右两个孩子，且全部叶子处在同一层。这个条件极强，它意味着只要某个节点有左孩子，就一定也有右孩子；只要某一层有节点，这一层就是满的。层与层之间不存在缺口，也就不需要在横向遍历时跳过空位。

第二个信号在进阶要求里：只允许常数级额外空间，递归的隐式栈不计入。这直接堵死了「开个队列做层序遍历」这条最省事的路，逼着解法去利用已经建好的 next 指针。

边界要想清楚两处：根为空时直接返回空；只有一个节点时没有任何 next 需要填，root.next 保持默认的空即可，循环一次都不该进。另外注意 next 字段初始就是空，所以「每层最右节点指向空」这件事不需要显式赋值。

解法：利用已连接层原地串联下一层

核心思路

最直接的做法是拿队列做层序遍历，每弹出一个节点就把它的 next 指向队列里同层的下一个节点。逻辑简单且对任意二叉树都成立，但队列在最宽的一层会存下约 n / 2 个节点，空间是 $O(n)$，正好违背进阶要求。瓶颈就在这个队列：它的唯一作用是「知道同一层里我右边是谁」。

于是问题变成：能不能不借助外部容器，就知道同层的右邻居是谁？答案藏在题目本身——我们正在填的 next 指针，恰恰就是「同层右邻居」这个信息的载体。

关键观察是分层递推：假设第 i 层的 next 已经全部填好，那么第 i 层就是一条可以横向走通的链表。沿着这条链表遍历第 i 层的每个父节点 cur，第 i + 1 层的所有连接都能就地补上。对同一个父节点，cur.left 的右邻居必然是 cur.right；对跨父节点的接缝，cur.right 的右邻居必然是 cur.next.left，这一步用到的正是第 i 层已经建好的 next。完美二叉树保证了 cur.next 存在时它一定有左孩子，所以这个引用永远安全。

不变量是：每轮外层循环开始时，leftmost 所在层的所有 next 指针都已正确填好，且 leftmost 是该层最左侧的节点。 第 0 层只有根，root.next 天然为空，不变量在起点成立；每轮内层循环把下一层填满，然后 leftmost 下移一层，不变量得以保持。当 leftmost.left 为空时说明已经到了叶子层，下面没有层可填，循环结束。

解题步骤

根为空直接返回空，避免后续解引用。

令 leftmost = root，作为「当前已连接层」的入口。之所以要单独维护这个变量，是因为横向遍历会把游标走到行尾，必须留一个指针记住每层的起点才能往下钻。

外层循环条件写成 leftmost.left != null。判据是「下一层是否存在」而不是「当前层是否存在」，因为循环体做的事情是填下一层；完美二叉树下左孩子为空就等价于当前层已是叶子层。

内层用 cur 从 leftmost 出发，沿着 cur = cur.next 横向走完整层。这一步就是用上一轮的成果代替队列。

对每个 cur 做两类连接。第一类 cur.left.next = cur.right 处理同父的兄弟，因为完美二叉树保证两个孩子都在，无需判空。第二类要先确认 cur.next != null 再写 cur.right.next = cur.next.left，处理相邻父节点之间的接缝；cur 是本层最后一个节点时 cur.next 为空，此时 cur.right 就是下一层最右节点，它的 next 保持默认空值正好符合要求。

一层处理完后执行 leftmost = leftmost.left，下移到刚刚连好的那一层，进入下一轮。

最后返回 root。整个过程只改指针不建节点，根引用始终有效。

以 [1,2,3,4,5,6,7] 走一遍：这是一棵三层的完美二叉树，根 1，第二层 2 和 3，第三层 4、5、6、7。初始 leftmost = 1，1.left 是 2 非空，进入第一轮。内层 cur = 1：先连 1.left.next = 1.right，即 2.next = 3；再看 1.next 为空，跳过跨父连接。cur = 1.next 变为空，内层结束，第二层已串成 2 → 3 → null。执行 leftmost = 1.left = 2。第二轮，2.left 是 4 非空，继续。内层 cur = 2：连 4.next = 5；2.next 是 3 非空，于是连 2.right.next = 2.next.left，即 5.next = 6。cur 前进到 3：连 6.next = 7；3.next 为空，跳过。cur 变空，内层结束，第三层串成 4 → 5 → 6 → 7 → null。执行 leftmost = 2.left = 4。第三轮判断 4.left 为空，外层退出。返回根 1，三层的 next 分别是 1 → null、2 → 3 → null、4 → 5 → 6 → 7 → null，与预期一致。

代码实现

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        Node leftmost = root;
        while (leftmost.left != null) {
            Node cur = leftmost;

            // 当前层已通过 next 串好，用它横向遍历并连接下一层。
            while (cur != null) {
                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }

            leftmost = leftmost.left;
        }

        return root;
    }
}

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }

    leftmost := root
    for leftmost.Left != nil {
        cur := leftmost

        // 当前层已通过 Next 串好，用它横向遍历并连接下一层。
        for cur != nil {
            cur.Left.Next = cur.Right
            if cur.Next != nil {
                cur.Right.Next = cur.Next.Left
            }
            cur = cur.Next
        }

        leftmost = leftmost.Left
    }

    return root
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是节点总数。每个节点作为 cur 被横向访问恰好一次，在那一次里做常数条指针赋值；各层节点数之和就是 $n$。

空间复杂度：$O(1)$，只用了 leftmost 和 cur 两个指针，没有队列也没有递归栈，满足进阶要求。

关键点总结

当题目要求把某种结构「填进原数据」时，可以反过来把已填好的部分当作遍历工具。这里第 i 层的 next 既是答案也是走到第 i 层每个父节点的通道，一份结构服务两个用途，队列因此被省掉。

分层递推的正确性依赖一个清晰的不变量：「当前层已连好」。想清楚不变量在起点如何成立、在每轮如何保持，代码的循环条件和更新顺序就自然确定了。

完美二叉树这个前提被用在了两处：内层不需要对 cur.left、cur.right 判空，以及 cur.next 存在时它必有左孩子。换成普通二叉树这两条都不成立，解法必须改造。

外层循环的判据是「下一层存不存在」，而不是「当前层存不存在」。凡是循环体在处理「下一步」的题，条件都应该照着下一步写，否则会多跑一轮踩空。

面试视角：先给出队列版层序遍历作为基线，再点明它 $O(n)$ 空间不满足进阶，然后引出「用 next 当队列」的思路，是这题最完整的展示路线。

面试视角：几乎必被追问「如果不是完美二叉树呢」，也就是第 117 题。要能答出：改用一个哑节点当下一层的表头、外加一个尾指针边扫边接，就能处理任意缺孩子的情形，且空间仍是常数。

易错点总结

错误写法：漏掉 cur.right.next = cur.next.left 这条跨父连接。用例 [1,2,3,4,5,6,7] → 第三层只连出 4 → 5 和 6 → 7 两段孤立的链，5.next 为空，整层没有串通。

错误写法：写跨父连接时不判 cur.next != null。用例 [1,2,3,4,5,6,7] → 内层走到本层最后一个父节点时 cur.next 为空，读它的 left 直接抛空指针异常。

错误写法：外层循环条件写成 leftmost != null。用例 [1,2,3,4,5,6,7] → leftmost 下移到第三层的 4 后仍会进入循环体，执行 cur.left.next 时 4.left 为空，立刻崩溃。

错误写法：内层结束后写 leftmost = leftmost.next 而不是 leftmost.left。用例 [1,2,3,4,5,6,7] → leftmost 在同层横向漂移，从 1 走到空后外层判空崩溃，或原地打转永远下不了一层。

错误写法：把两条连接的顺序写成先跨父后同父，并且中途覆盖了要用的引用，例如先执行 cur.right = cur.next.left（少写了 .next）。用例 [1,2,3,4,5,6,7] → 直接把右孩子指针改掉，树结构被破坏，后续遍历全乱。

错误写法：单节点树时仍然进入内层并访问 root.left.next。用例 [1] → 外层条件若误写成先执行后判断（例如用 do-while），会在空的左孩子上解引用异常，而正确行为是一次都不进循环。

错误写法：显式给每层最右节点写 cur.right.next = null 却把它放在了跨父连接之后、没有加 else。用例 [1,2,3,4,5,6,7] → 刚连好的 5.next = 6 被随即清空，第三层重新断开。

错误写法：把这套写法原样搬到非完美二叉树上。用例 [1,2,3,4,null,null,7] → 2.right 为空时 cur.left.next = cur.right 虽不报错但连了个空，随后 cur.next.left 也可能为空，整层链断裂，这正是第 117 题需要另写的原因。

错误写法：改用递归对每个节点分别处理，认为空间仍是常数。用例退化程度高的树 → 递归栈深度等于树高，完美二叉树下是 $O(\log n)$，但这已经不是题目要求的严格常数空间，面试中会被追问。

相似题目

题目	难度	考察点
117. 填充每个节点的下一个右侧节点指针 II	中等	允许缺孩子，需用哑节点加尾指针边扫边接
102. 二叉树的层序遍历	中等	输出按层分组的值，需显式记录每层节点数
199. 二叉树的右视图	中等	只取每层最后一个节点，可用深搜按深度首见
103. 二叉树的锯齿形层序遍历	中等	层内方向交替，需要按奇偶层反转或双端插入
662. 二叉树最大宽度	中等	给节点编号计算层内跨度，含大数下标溢出处理
114. 二叉树展开为链表	中等	按前序而非按层重排指针，同样要求原地完成