【题目描述】
给定一个二叉树:
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
【示例一】
输入:root = [1,2,3,4,5,null,7] 输出:[1,#,2,3,#,4,5,7,#] 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。
【示例二】
输入:root = [] 输出:[]
【提示及数据范围】
- 树中的节点数在范围
[0, 6000]
内 -100 <= Node.val <= 100
【代码】
// 方法一:层次遍历
class Solution {
public:
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
Node *last = nullptr;
for (int i = 1; i <= n; ++i) {
Node *f = q.front();
q.pop();
if (f->left) {
q.push(f->left);
}
if (f->right) {
q.push(f->right);
}
if (i != 1) {
last->next = f;
}
last = f;
}
}
return root;
}
};
// 方法二:使用已建立的 next 指针
class Solution {
public:
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
};