填充每个节点的下一个右侧节点指针 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.nextreturnrootC++
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）
)
)