06、填充每个节点的下一个右侧节点指针II
大约 5 分钟数据结构算法算法基地面试二叉树层序遍历刷题程序厨校招社招
该题目相比上面的，稍微有点难度，题目理解起来有点吃力，我们一块来看一下吧
题目描述
给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL****。
初始状态下，所有 next 指针都被设置为 NULL。
看到这里可能还有点懵懵的，不过直接看下图的示例就好了
示例 1：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
输入的二叉树：
1
/ \
2 3
/ \ \
4 5 7
输出（填充后）：
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4 ->5 -> 7 -> NULL
示例 2：
输入：root = []
输出：[]
数据范围：
- 树中节点数目在范围
[0, 6000]内 -100 <= Node.val <= 100
进阶要求：
- 你只能使用常量级额外空间
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度
题目分析
这道题要求将同一层的节点用 next 指针连接起来。懂了，也就是每一层建立一个单链表
核心思路
每一层的节点从左到右依次用 next 指针连接，最右边的节点指向 NULL，但是各位注意，这里
关键点
- 需要按层遍历
- 需要在同一层建立连接
- 与 LeetCode 116 的区别：本题的树不一定是完美二叉树
层序遍历+队列
算法思路
- 使用队列进行层序遍历
- 遍历每一层时，将相邻节点用
next指针连接 - 每层最后一个节点的
next保持为NULL
图解过程
以 root = [1,2,3,4,5,null,7] 为例：
第 1 层：
队列：[1]
1 -> NULL
第 2 层：
队列：[2, 3]
2 -> 3 -> NULL
第 3 层：
队列：[4, 5, 7]
4 -> 5 -> 7 -> NULL
C++ 实现
#include <queue>
using namespace std;
/**
* Definition for a Node.
*/
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
class Solution {
public:
Node* connect(Node* root) {
if (root == nullptr) {
return nullptr;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
Node* node = q.front();
q.pop();
// 如果不是当前层的最后一个节点，连接到下一个节点
if (i < levelSize - 1) {
node->next = q.front();
}
// 将子节点加入队列
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
return root;
}
};
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(w)，其中 w 是二叉树的最大宽度。队列中最多存储一层的节点。
这种做法，大家都可以搞定，但是不符合题目要求，空间复杂度为 O(n)，所以我们要使用其他方法来解决
O(1) 空间的层序遍历
算法思路
题目要求，我们O(1)的空间复杂度完成该题，所以我们来思考一下如何完成呢？
我们可以不使用队列，而是利用已经建立好的 next 指针来遍历每一层。
关键点
- 使用
leftmost记录每层的最左节点，相当于一个虚节点，用来记录该层最左边的节点，然后做为本层链表的起点 - 使用已建立的
next指针遍历当前层 - 在遍历当前层的同时，建立下一层的
next连接
C++ 实现
class Solution {
public:
Node* connect(Node* root) {
if (root == nullptr) {
return nullptr;
}
// leftmost 指向每层的最左节点
Node* leftmost = root;
while (leftmost != nullptr) {
// 用于连接下一层节点的虚拟头节点
Node dummy(0);
// 这里比较重要，用来遍历下一层，dummy 是虚节点，其 next 就是下一层的最左边的节点
Node* prev = &dummy;
// 遍历当前层
Node* curr = leftmost;
while (curr != nullptr) {
// 处理左子节点
if (curr->left) {
prev->next = curr->left; // 构建链表
prev = prev->next;
}
// 处理右子节点
if (curr->right) {
prev->next = curr->right;
prev = prev->next;
}
// 移动到当前层的下一个节点
curr = curr->next;
}
// 当前层遍历完毕，移动到下一层
leftmost = dummy.next;
}
return root;
}
};
图解过程
1
/ \
2 3
/ \ \
4 5 7
第 1 步：处理第 1 层（1）
curr = 1, 连接 2 -> 3
leftmost = 2
第 2 步：处理第 2 层（2 -> 3）
curr = 2, 连接 4 -> 5
curr = 3, 连接 5 -> 7
leftmost = 4
第 3 步：处理第 3 层（4 -> 5 -> 7）
没有子节点，leftmost = nullptr
结束
复杂度分析
- 时间复杂度：O(n)，每个节点被访问一次。
- 空间复杂度：O(1)，只使用了常量级额外空间。
