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

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

题目描述

给定一个二叉树：

ts
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

示例 1

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

示例 2

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

约束

  • 树中的节点数在范围 [0, 6000] 内
  • -100 <= Node.val <= 100

进阶

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

核心思路

这题和 116 很像，但最关键的区别是：

  • 这里 不是完美二叉树

也就是说：

  • 某个节点可能没有左孩子
  • 也可能没有右孩子
  • node.next.left 不一定存在

所以 116 那种“直接用固定结构连接”的方法，不能原样照搬。

这题至少有两种常见做法：

  • 解法一：BFS 按层连接（推荐先理解）
  • 解法二：用虚拟头节点按层串下一层（最优做法）

解法一：BFS 按层连接

这是最直观的做法。

思路拆解

和普通层序遍历一样：

  • 同一层的节点会依次出队
  • 前一个节点的 next 指向后一个节点
  • 每层最后一个节点的 next 留为 null

因为这题树结构不规则，所以 BFS 反而更容易直接写对。

一步一步写出算法

第一步：处理空树

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]
    }
    ...
}

第五步：加入下一层真实存在的孩子

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

代码实现（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 指针横向遍历这一层
  • 在遍历过程中，把下一层节点重新串起来

为此我们引入两个指针：

  • dummy：下一层链表的虚拟头节点
  • tail：下一层链表当前尾巴

处理当前层每个节点时：

  • 如果它有左孩子，就接到 tail.next
  • 如果它有右孩子，也接到 tail.next

这样一轮处理完后：

  • dummy.next 就是下一层最左节点
  • 下一层所有节点也已经用 next 串起来了

然后继续处理下一层。

一步一步写出算法

第一步：从当前层最左节点开始

ts
let current: Node | null = root

第二步：每次处理整一层

ts
while (current !== null) {
    const dummy = new Node(0)
    let tail = dummy
    ...
}

第三步：横向遍历当前层

ts
let node: Node | null = current
while (node !== null) {
    ...
    node = node.next
}

第四步：把下一层孩子接起来

ts
if (node.left !== null) {
    tail.next = node.left
    tail = tail.next
}

if (node.right !== null) {
    tail.next = node.right
    tail = tail.next
}

第五步：进入下一层

ts
current = dummy.next

代码实现（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 {
    let current: Node | null = root

    while (current !== null) {
        const dummy = new Node(0)
        let tail = dummy
        let node: Node | null = current

        while (node !== null) {
            if (node.left !== null) {
                tail.next = node.left
                tail = tail.next
            }

            if (node.right !== null) {
                tail.next = node.right
                tail = tail.next
            }

            node = node.next
        }

        current = dummy.next
    }

    return root
}

复杂度分析

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

这一解法的优缺点

优点：

  • 满足进阶要求
  • 是这题标准最优解
  • 对一般二叉树也适用

缺点：

  • 比 116 更绕一点
  • 需要理解“当前层串下一层”这个技巧

两种解法对比

解法时间复杂度空间复杂度特点
BFS 按层连接O(n)O(n)最直观
虚拟头节点串下一层O(n)O(1)最优，最推荐

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

手动模拟一遍最优解

以：

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

为例。

第 1 层

当前层只有 1。

遍历 1 时，把下一层接成：

text
2 -> 3

第 2 层

当前层是：

text
2 -> 3

遍历 2：

  • 接上 4
  • 接上 5

遍历 3：

  • 没有左孩子
  • 接上 7

于是下一层变成：

text
4 -> 5 -> 7

这就是答案要求的连接结果。

面试时最容易错的点

1. 这题不是完美二叉树

所以不能照抄 116 的：

ts
node.right.next = node.next.left

因为 node.next.left 可能不存在。

2. 虚拟头节点是关键技巧

dummy 的作用就是：

  • 统一收集下一层的第一个节点
  • 避免写很多“这一层第一个节点是谁”的特殊判断

3. 当前层是靠 next 横向走，不是靠队列

在最优解里：

  • node = node.next

这是核心。

一句话总结

这题的本质是：

一边沿当前层的 next 横向遍历，一边把下一层重新用 next 串起来。

  • 想先写稳：用 BFS
  • 想写最优解：用 虚拟头节点串下一层

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

ts
function connect(root: Node | null): Node | null {
    let current: Node | null = root

    while (current !== null) {
        const dummy = new Node(0)
        let tail = dummy
        let node: Node | null = current

        while (node !== null) {
            if (node.left !== null) {
                tail.next = node.left
                tail = tail.next
            }

            if (node.right !== null) {
                tail.next = node.right
                tail = tail.next
            }

            node = node.next
        }

        current = dummy.next
    }

    return root
}

因为这个版本：

  • 适用于一般二叉树
  • 满足常量额外空间要求
  • 是这题公认的标准写法