0116. Populating Next Right Pointers in Each Node¶
题目信息¶
- 题号:
填充每个节点的下一个右侧节点指针
- 难度:
Medium
- 主题:
完美二叉树、层序遍历、横向链、常量空间
- 原题:
- 重点:
从队列保存整层,推导出完美树的同父与跨父两类连接,并复用已建立的 next 链遍历下一层父节点
题目重述¶
给定一棵完美二叉树的根节点 root。每个节点除 left、right 外还有 next 指针,需要把它设置
为同一层紧邻的右侧节点;每层最右节点的 next 必须为 nullptr。完成后返回原根节点。
完美二叉树中,每个非叶节点恰有两个孩子,所有叶节点位于同一深度。树中节点总数在
0..2^12 - 1 范围内,节点值在 -1000..1000 范围内。进阶目标是只使用常量额外空间。
自建示例¶
三层完美树:
root = [10,4,16,2,6,14,18],按#表示层尾时,连接结果为[10,#,4,16,#,2,6,14,18,#];跨父连接:上例第三层中
6.next必须指向14,不能只连接同一父节点的两个孩子;单节点:
root = [7],7.next为nullptr;空树:
root = [],返回nullptr。
C++ 实现¶
#include <queue>
class Solution {
private:
Node* connectWithQueue(Node* root) {
if (!root) {
return nullptr;
}
std::queue<Node*> pending;
pending.push(root);
while (!pending.empty()) {
const int levelSize = static_cast<int>(pending.size());
Node* previous = nullptr;
for (int count = 0; count < levelSize; ++count) {
Node* node = pending.front();
pending.pop();
if (previous) {
previous->next = node;
}
previous = node;
if (node->left) {
pending.push(node->left);
}
if (node->right) {
pending.push(node->right);
}
}
previous->next = nullptr;
}
return root;
}
Node* connectPerfectTree(Node* root) {
if (!root) {
return nullptr;
}
root->next = nullptr;
for (Node* leftmost = root; leftmost->left; leftmost = leftmost->left) {
for (Node* current = leftmost; current; current = current->next) {
current->left->next = current->right;
current->right->next = current->next ? current->next->left : nullptr;
}
}
return root;
}
public:
Node* connect(Node* root) {
return connectPerfectTree(root);
}
};
题解¶
队列保存层边界¶
最直接的正确方法是层序遍历。connectWithQueue 在每轮开始时固定当前层大小,按从左到右顺序弹出节点;
previous 保存本层上一个节点,当前节点到达时令 previous->next = node,层结束后把最后节点连接到空。
队列保证不同深度不会混合,每层相邻节点恰好在连续两次弹出中出现,所以所有 next 都会设置一次。这个
方案适用于任意二叉树,时间 O(n),但为了知道当前节点右边是谁,队列最多保存一整层 O(w) 个节点。
完美树的新信息¶
完美树让下一层的相邻关系只有两种。对当前层父节点 current:
同父孩子:current.left.next = current.right
跨父孩子:current.right.next = current.next.left
第二条只在 current->next 存在时成立;当前父节点若是层尾,它的右孩子也是下一层层尾,应连接
nullptr。完美树保证每个正在处理的父节点都有左右孩子,也保证右侧相邻父节点必有左孩子,因此不需要
搜索“下一个实际存在的孩子”。
这两类关系覆盖全部相邻对:下一层任意两个相邻节点要么共享父节点,要么分别是两个相邻父节点的右孩子与
左孩子。队列中保存整层的目的可以改由当前层已经建立的 next 链承担。
逐层复用横向链¶
connectPerfectTree 处理某层前保持不变量:该层已经通过 next 从左到右完整连接,层尾指向空。根层
只有一个节点,显式设置 root->next = nullptr 后满足基础情况。
内层循环从 leftmost 开始,沿 current = current->next 访问当前层全部父节点,同时用上面的两条
规则建立下一层。处理完成后,下一层也形成完整横向链;外层令 leftmost = leftmost->left,进入下一层
最左节点。到达叶层时 leftmost->left 为空,不再尝试访问孩子。
因此算法并非在使用尚未构造的 next:当前层链在上一轮已经完成,当前轮只写下一层。这个先后关系是
常量空间方案成立的核心不变量。
连接走读¶
对 [10,4,16,2,6,14,18]:
当前父节点 |
同父连接 |
|
跨父或层尾连接 |
|---|---|---|---|
10 |
|
空 |
|
4 |
|
16 |
|
16 |
|
空 |
|
处理根后,第二层已有 4 -> 16 -> null,于是下一轮可以从 4 横向走到 16。在 4 处通过
4.next.left 找到 14,正好完成跨父连接 6 -> 14。
分支与主解选择¶
代码始终主动写根和每层尾部的空指针,使结果不依赖节点原有 next 内容。内层两次赋值顺序可以交换,
因为读取的是当前层父节点的 next,写入的是下一层孩子的 next,两者不冲突。
公开入口采用完美树常量空间方案,因为题目保证正好消除了寻找缺失孩子的需求;队列法仍作为从层序定义出发
的通用基线。若树不是完美树,current->next->left 可能为空甚至不存在,当前两条固定规则便不足以覆盖
下一层,不能直接套用。
复杂度分析¶
两种方法都处理每个节点常数次,时间 O(n)。队列法工作空间 O(w);主解只保存 leftmost、
current 等常数个指针,额外空间 O(1)。所有连接写入原节点,返回值只是原根指针。