题目描述
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| if (!root)return root;
queue<Node*> q;
Node* t = root;
q.push(t);
while (!q.empty())
{
t = q.front();
q.pop();
if (t->left&&t->right) {
q.push(t->left);
q.push(t->right);
}
if (!q.empty())
t->next = q.front();
else
t->next = NULL;
}
t = root;
while (t->right)
{
t->next = NULL;
t = t->right;
}
return root;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| Node* connect(Node* root) {
if (!root)return root;
queue<Node*> q;
Node* t = root;
q.push(t);
int level = 1;
while (!q.empty())
{
t = q.front();
q.pop();
if (t->left&&t->right) {
q.push(t->left);
q.push(t->right);
}
if (q.empty()||q.size() == pow(2, level))
{
t->next = NULL;
level++;
}
else
t->next = q.front();
}
return root;
}
|