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

约 5 分钟
文章信息 9 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 2-5 字节 微软 拼多多
标签
深度优先搜索 树 广度优先搜索 二叉树 链表

题目描述

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

image-20260928224314380

image-20260928224314384

题意分析

输入是一棵完美二叉树：每个非叶节点都有两个孩子，所有叶子位于同一层。需要为每个节点的 next 指向同层紧邻右侧的节点，每层最右节点指向空，原左右孩子连接保持不变。

题目保证初始 next 都为空。普通层序遍历可以借助队列寻找相邻节点，但这里树形完整，可以直接利用已经连好的当前层，建立下一层的连接，实现常数额外空间。

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

核心思路

[!blue]

用 leftmost 保存当前层最左节点，每轮开始时，这一层的 next 已经连接完整。根层只有一个节点，初始 next 为空，天然满足这个条件，因此可以从根层开始。

沿当前层的 next 从左到右访问父节点 cur。下一层相邻节点的关系只有两类：同一个父节点的左孩子后面是右孩子，设置 cur.left.next = cur.right；这个右孩子后面则是相邻父节点的左孩子，若 cur.next 存在，就设置 cur.right.next = cur.next.left。

两类连接覆盖了下一层的全部相邻位置。当前层最右父节点没有后继，它的右孩子也是下一层最右节点，不再设置后继，保留初始的空指针即可。处理时只改孩子的 next，不会影响正在用来横向遍历的当前层连接。

整层完成后，下一层已经连好，将 leftmost 移到它的左孩子，再重复相同过程。完美树保证只要最左节点有孩子，这一层的所有父节点就都有两个孩子，可以安全使用上述直接连接。

当 leftmost.left 为空，当前层就是叶子层，不需要再连接下一层，循环结束。空树在入口返回，只有根节点时也会自然跳过外层循环。

解题步骤

  1. 根为空时直接返回空，否则令 leftmost = root。
  2. 当前层仍有孩子时，从 leftmost 开始沿 next 横向遍历。
  3. 对每个父节点，先把左孩子的 next 连到右孩子。
  4. 若存在相邻父节点，再把右孩子的 next 连到它的左孩子。
  5. 当前层全部处理后，令 leftmost = leftmost.left，进入刚连接好的下一层，最后返回原根。

代码实现

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)$，各非叶节点作为父节点处理一次，叶节点无须再展开。
  • 空间复杂度：$O(1)$，两个遍历指针。

关键点总结

[!green]

  • 当前层的答案同时充当遍历下一层的工具。
  • 完美树条件保证同层父节点都有两个孩子。

易错点总结

[!yellow]

  • 只连接同父兄弟：会遗漏不同父节点之间的接缝，下一层不能完整横向遍历。
  • 跨父连接不检查 cur.next：最右父节点没有后继，直接读取它的孩子会访问空指针。
  • 到叶子层仍继续展开：叶子没有左右孩子，外层应在下一层不存在时停止。
  • 把写法用于任意二叉树：直接连接依赖完美树条件，缺失孩子时不能照搬。

相似题目

题目 难度 关联与区别
117. 填充每个节点的下一个右侧节点指针 II 中等 本题完美二叉树可直接跨父节点连邻居，原题缺失节点较多，需要动态寻找下一层可用节点。
102. 二叉树的层序遍历 中等 层序遍历可直观定位同层后继，本题还可利用已建next链省掉队列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/44904513
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！