面试经典150题[074]：填充每个节点的下一个右侧节点指针 II（LeetCode 117）

填充每个节点的下一个右侧节点指针 II（LeetCode 117）

题目链接：填充每个节点的下一个右侧节点指针 II（LeetCode 117）
难度：中等

1. 题目描述

给你一个二叉树的根节点root，请你将其中所有节点的next指针指向其右侧的节点。如果没有右侧节点，则next指针应设置为NULL。

初始时，所有next指针都设置为NULL。

树节点定义：

classNode:def__init__(self,val:int=0,left:'Node'=None,right:'Node'=None,next:'Node'=None):self.val=val self.left=left self.right=right self.next=next

要求：

• 二叉树不一定是完美的（即不一定是满二叉树或完全二叉树）。
• 节点数 0 <= n <= 6000
• -100 <= Node.val <= 100

示例：

输入: root = [1,2,3,4,5,null,7] 输出: [1,#,2,3,#,4,5,7,#] 解释: 给定二叉树如图所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

输入: root = [] 输出: []

2. 问题分析

2.1 规律

• 这是一个二叉树问题，需要将同一层的节点通过next指针连接起来，形成一个链表。
• 与 LeetCode 116 不同，本题的树不一定是完美的，因此不能假设每层都有完整的左右子节点。
• 核心问题：如何在不使用额外空间（如队列）的情况下，高效连接同一层节点？
• 类似于层序遍历，但需要处理缺失节点的情况。

2.2 贪心思路

我们使用常量空间的层级连接方法：

• 从根节点开始，逐层处理。
• 对于每一层，使用一个虚拟节点dummy来构建下一层的链表头，并用tail指针来连接下一层的子节点。
• 遍历当前层的节点（通过已连接的next指针），为每个节点的左右子节点建立连接：
  • 如果有左子节点，连接到tail.next。
  • 如果有右子节点，连接到tail.next。
• 当前层遍历结束后，将下一层的头节点设置为dummy.next，继续处理下一层。
• 这个方法利用了上一层的next指针来遍历当前层，避免使用队列，实现 O(1) 额外空间。
• 如果树为空或只有根节点，直接返回。

3. 代码实现

Python

classSolution:defconnect(self,root:'Node')->'Node':ifnotroot:returnroot head=rootwhilehead:dummy=Node(0)tail=dummy cur=headwhilecur:ifcur.left:tail.next=cur.left tail=tail.nextifcur.right:tail.next=cur.right tail=tail.nextcur=cur.nexthead=dummy.nextreturnroot

C++

classSolution{public:Node*connect(Node*root){if(!root)returnroot;Node*head=root;while(head){Node*dummy=newNode(0);Node*tail=dummy;Node*cur=head;while(cur){if(cur->left){tail->next=cur->left;tail=tail->next;}if(cur->right){tail->next=cur->right;tail=tail->next;}cur=cur->next;}head=dummy->next;// 注意：在C++中，需要手动删除dummy以避免内存泄漏，但LeetCode环境可忽略}returnroot;}};

4. 复杂度分析

• 时间复杂度：O(n)，遍历每个节点一次。
• 空间复杂度：O(1)，只使用常量额外空间（不计递归栈或队列）。

5. 总结

• 连接 next 指针问题+非完美二叉树→ 使用虚拟节点构建下一层链表是首选。
• 核心维护dummy和tail，很通用。
  • 类似于优化后的 BFS 层序遍历，但空间为 O(1)。
  • 可扩展到完美二叉树的变体（LeetCode 116）。

复习

面试经典150题[014]：加油站（LeetCode 134）
面试经典150题[044]：两数之和（LeetCode 1）
面试经典150题[059]：合并两个有序链表（LeetCode 21）