Populating Next Right Pointers in Each Node
给了一个完美的二叉树, 填充其next节点
my solution (60ms, 90.37%)
这道题我给出了两种方案, 递归和迭代
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| static const int _ = [] () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
} ();
class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
connect_two(root->left, root->right);
return root;
}
void connect_two(Node* left, Node* right) {
if (!left) return;
left->next = right;
if (left->left)
connect_two(left->left, left->right);
connect_two(left->right, right->left);
connect_two(right->left, right->right);
}
};
|
对于迭代, 我将每一级的元素都保留, 然后用作下一次迭代
递归的话, 因为如果只是单节点传参, 始终会面临有缝隙的情况, 所以用双节点传参
递归的代码更加简洁, 我推荐使用递归
emmmm… 速度上还好, 但是内存上就很不能接受了
(我很好奇, 代码量已经很少了, 而且递归中也不会产生多余的操作)
(难道是在 perfect binary tree 上能有什么绚丽的操作么?)
best solution
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
26
27
28
29
30
31
| void connect(TreeLinkNode *root) {
queue<TreeLinkNode*> q;
if (!root){
return;
}
q.push(root);
while (!q.empty()){
int size = q.size();
while (size--){
TreeLinkNode* c = q.front();
q.pop();
if (size == 0){
c->next = NULL;
}
else{
c->next = q.front();
}
if (c->left){
q.push(c->left);
}
if (c->right){
q.push(c->right);
}
}
}
return;
}
|
哦哦哦, 用的是迭代的方式, 只不过他用了队列
而且用了size, 这样也就不需要一个新的容器了, 很不错 -v-
不过既然题说了是 perfect binary tree, 而且next默认为空, 那么可以稍微改良一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| Node* connect(Node* root) {
if (!root) return root;
queue<Node*> q;
q.push(root);
while( !q.empty() ) {
int size = q.size();
while (size--) {
Node* cur = q.front();
q.pop();
if (size)
cur->next = q.front();
if (cur->left) {
q.push(cur->left);
q.push(cur->right);
}
}
}
return root;
}
|
细节在于:
- 如果是空节点, 少了一个空 queue 的分配时间
- 不用再去赋值 nullptr 了
- 少了一个 cur->right 的判断, 因为题目说了是 perfect binary tree
PS: 我最后用这个答案再试了一次, 发现结果和我用递归的结果相差无几…
可能这是增加了测试用例或者改了题的结果? 毕竟 TreeLinkNode 变为了 Node