http://www.geeksforgeeks.org/connect-nodes-at-same-level-with-o1-extra-space/
recursive:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
using
namespace
std;
9
10
struct
node {
11
int
data;
12
struct
node *left, *right, *
next;
13
node() : data(
0
), left(NULL), right(NULL), next(NULL) { }
14
node(
int
d) : data(d), left(NULL), right(NULL), next(NULL) { }
15
};
16
17
node *getnext(node *
root) {
18
node *next = root->
next;
19
while
(next) {
20
if
(next->left)
return
next->
left;
21
if
(next->right)
return
next->
right;
22
next = next->
next;
23
}
24
return
NULL;
25
}
26
27
void
_connect(node *
root) {
28
if
(!root)
return
;
29
if
(root->next) _connect(root->
next);
30
if
(root->
left) {
31
if
(root->
right) {
32
root->left->next = root->
right;
33
root->right->next =
getnext(root);
34
}
35
else
root->left->next =
getnext(root);
36
_connect(root->
left);
37
}
38
else
if
(root->
right) {
39
root->right->next =
getnext(root);
40
_connect(root->
right);
41
}
42
else
_connect(root->
next);
43
}
44
45
void
connect(node *
root) {
46
if
(!root)
return
;
47
root->next =
NULL;
48
_connect(root);
49
}
50
51
int
main() {
52
node *root =
new
node(
10
);
53
root->left =
new
node(
8
);
54
root->right =
new
node(
2
);
55
root->left->left =
new
node(
3
);
56
root->right->right =
new
node(
90
);
57
connect(root);
58
cout << root->data <<
"
->
"
<< (root->next? root->next->data : -
1
) <<
endl;
59
cout << root->left->data <<
"
->
"
<< (root->left->next? root->left->next->data : -
1
) <<
endl;
60
cout << root->right->data <<
"
->
"
<< (root->right->next? root->right->next->data : -
1
) <<
endl;
61
cout << root->left->left->data <<
"
->
"
<< (root->left->left->next? root->left->left->next->data : -
1
) <<
endl;
62
cout << root->right->right->data <<
"
->
"
<< (root->right->right->next? root->right->right->next->data : -
1
) <<
endl;
63
return
0
;
64
}
iterative(better)
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
using
namespace
std;
9
10
struct
node {
11
int
data;
12
struct
node *left, *right, *
next;
13
node() : data(
0
), left(NULL), right(NULL), next(NULL) { }
14
node(
int
d) : data(d), left(NULL), right(NULL), next(NULL) { }
15
};
16
17
node *getnext(node *
root) {
18
node *next = root->
next;
19
while
(next) {
20
if
(next->left)
return
next->
left;
21
if
(next->right)
return
next->
right;
22
next = next->
next;
23
}
24
return
NULL;
25
}
26
27
void
connect(node *
root) {
28
if
(!root)
return
;
29
root->next =
NULL;
30
while
(root) {
31
node *p =
root;
32
while
(p) {
33
if
(p->
left) {
34
if
(p->right) p->left->next = p->
right;
35
else
p->left->next =
getnext(p);
36
}
37
if
(p->right) p->right->next =
getnext(p);
38
p = p->
next;
39
}
40
if
(root->left) root = root->
left;
41
else
if
(root->right) root = root->
right;
42
else
root = root->
next;
43
}
44
}
45
46
int
main() {
47
node *root =
new
node(
10
);
48
root->left =
new
node(
8
);
49
root->right =
new
node(
2
);
50
root->left->left =
new
node(
3
);
51
root->right->right =
new
node(
90
);
52
connect(root);
53
cout << root->data <<
"
->
"
<< (root->next? root->next->data : -
1
) <<
endl;
54
cout << root->left->data <<
"
->
"
<< (root->left->next? root->left->next->data : -
1
) <<
endl;
55
cout << root->right->data <<
"
->
"
<< (root->right->next? root->right->next->data : -
1
) <<
endl;
56
cout << root->left->left->data <<
"
->
"
<< (root->left->left->next? root->left->left->next->data : -
1
) <<
endl;
57
cout << root->right->right->data <<
"
->
"
<< (root->right->right->next? root->right->right->next->data : -
1
) <<
endl;
58
return
0
;
59
}
Data Structure Binary Tree: Connect nodes at same level using constant extra space
