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

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

题目描述

给定一个 完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。

请你填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 设置为 null。

初始状态下，所有 next 指针都被设置为 null。

示例 1

text
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]

示例 2

text
输入：root = []
输出：[]

约束

  • 树中节点的数量在 [0, 2^12 - 1] 范围内
  • -1000 <= Node.val <= 1000

进阶

  • 你只能使用常量级额外空间
  • 递归解法中隐式栈空间不算额外空间

核心思路

这题的重点在于：

  • 树是 完美二叉树

这意味着：

  • 每个非叶子节点一定有左右两个孩子
  • 同一层一定排得很整齐

所以这题至少有两种经典做法：

  • 解法一：BFS 按层连接（推荐先理解）
  • 解法二：利用已建立的 next 指针按层推进（最优做法）

解法一：BFS 按层连接

这是最直观的做法。

思路拆解

按层遍历时：

  • 同一层的节点会按从左到右顺序被取出来
  • 所以前一个节点的 next，直接指向后一个节点即可

每层最后一个节点的 next 保持 null。

一步一步写出算法

第一步：处理空树

ts
if (root === null) {
    return null
}

第二步：准备队列

ts
const queue: Node[] = [root]

第三步：按层遍历

ts
while (queue.length > 0) {
    const size = queue.length
    ...
}

第四步：连接同层节点

ts
for (let i = 0; i < size; i++) {
    const node = queue.shift()!
    if (i < size - 1) {
        node.next = queue[0]
    }
    ...
}

第五步：加入下一层

因为是完美二叉树，所以左右孩子存在时都可以入队。

代码实现（TypeScript）

ts
class Node {
    val: number
    left: Node | null
    right: Node | null
    next: Node | null
    constructor(val?: number, left?: Node | null, right?: Node | null, next?: Node | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
        this.next = next ?? null
    }
}

function connect(root: Node | null): Node | null {
    if (root === null) {
        return null
    }

    const queue: Node[] = [root]

    while (queue.length > 0) {
        const size = queue.length

        for (let i = 0; i < size; i++) {
            const node = queue.shift()!
            if (i < size - 1) {
                node.next = queue[0]
            }

            if (node.left !== null) {
                queue.push(node.left)
            }
            if (node.right !== null) {
                queue.push(node.right)
            }
        }
    }

    return root
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

这一解法的优缺点

优点：

  • 最直观
  • 最适合第一次理解

缺点：

  • 没满足常量额外空间进阶要求

解法二：利用 next 指针按层推进

这是这题最经典的最优做法。

思路拆解

因为是完美二叉树，所以对于当前层的某个节点 node：

  1. node.left.next = node.right
  2. 如果 node.next !== null，那么：
    • node.right.next = node.next.left

这两条规则就足够把下一层整层都连起来。

然后我们按层从左往右推进：

  • 当前层用 next 指针横着走
  • 下一层连接好后，再下降到下一层最左节点继续处理

一步一步写出算法

第一步：处理空树

ts
if (root === null) {
    return null
}

第二步：从最左节点开始逐层处理

ts
let leftmost = root
while (leftmost.left !== null) {
    ...
}

为什么可以直接看 leftmost.left？

因为它是完美二叉树，非叶子一定有左孩子。

第三步：横向遍历当前层

ts
let head: Node | null = leftmost
while (head !== null) {
    ...
    head = head.next
}

第四步：连接下一层

ts
head.left!.next = head.right

if (head.next !== null) {
    head.right!.next = head.next.left
}

第五步：下降到下一层

ts
leftmost = leftmost.left

代码实现（TypeScript）

ts
class Node {
    val: number
    left: Node | null
    right: Node | null
    next: Node | null
    constructor(val?: number, left?: Node | null, right?: Node | null, next?: Node | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
        this.next = next ?? null
    }
}

function connect(root: Node | null): Node | null {
    if (root === null) {
        return null
    }

    let leftmost: Node | null = root

    while (leftmost.left !== null) {
        let head: Node | null = leftmost

        while (head !== null) {
            head.left!.next = head.right

            if (head.next !== null) {
                head.right!.next = head.next.left
            }

            head = head.next
        }

        leftmost = leftmost.left
    }

    return root
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1) 额外空间

这一解法的优缺点

优点：

  • 满足进阶要求
  • 非常巧妙
  • 是这题标准最优解

缺点：

  • 依赖“完美二叉树”这个特殊条件

两种解法对比

解法时间复杂度空间复杂度特点
BFS 按层连接O(n)O(n)最直观
利用 next 按层推进O(n)O(1)最优，最推荐

如果你是第一次做这题，建议先理解 BFS，再掌握第二种。

手动模拟一遍最优解

以：

text
        1
      /   \
     2     3
    / \   / \
   4  5  6   7

为例。

第 1 层

节点 1：

  • 2.next = 3

第 2 层

节点 2：

  • 4.next = 5
  • 5.next = 6（因为 2.next = 3）

节点 3：

  • 6.next = 7

最终下一层就都连好了。

面试时最容易错的点

1. 这题利用了“完美二叉树”条件

116 能用常量空间漂亮解决，是因为：

  • 每个父节点都有两个孩子
  • head.next.left 一定存在

2. node.right.next = node.next.left 这一句很关键

这是跨父节点连接的核心。

3. BFS 虽然能做，但不是最优

进阶要求更推荐第二种。

一句话总结

这题的本质是：

利用完美二叉树的结构规律，把同层节点通过 next 串起来。

  • 想先理解：用 BFS
  • 想写最优解：用 利用 next 的 O(1) 做法

推荐你最后记住的标准写法

ts
function connect(root: Node | null): Node | null {
    if (root === null) {
        return null
    }

    let leftmost: Node | null = root

    while (leftmost.left !== null) {
        let head: Node | null = leftmost

        while (head !== null) {
            head.left!.next = head.right

            if (head.next !== null) {
                head.right!.next = head.next.left
            }

            head = head.next
        }

        leftmost = leftmost.left
    }

    return root
}

因为这个版本：

  • 最能体现题目特殊结构
  • 空间复杂度最优
  • 是这题公认的标准解法