1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
void
prints(node *
root) {
19
if
(!root)
return
;
20
prints(root->
left);
21
cout << root->data <<
"
"
;
22
prints(root->
right);
23
}
24
25
node *_buildtree(
int
pre[],
int
post[],
int
&preindex,
int
l,
int
h,
int
size) {
26
if
(preindex >= size || l > h)
return
NULL;
27
node *root =
new
node(pre[preindex++
]);
28
if
(l == h)
return
root;
29
int
i =
l;
30
for
(; i <= h; i++)
if
(pre[preindex] == post[i])
break
;
31
if
(i <=
h) {
32
root->left =
_buildtree(pre, post, preindex, l, i, size);
33
root->right = _buildtree(pre, post, preindex, i+
1
, h, size);
34
}
35
return
root;
36
}
37
38
node *buildtree(
int
pre[],
int
post[],
int
size) {
39
int
preindex =
0
;
40
return
_buildtree(pre, post, preindex,
0
, size-
1
, size);
41
}
42
43
int
main() {
44
int
pre[
9
] = {
1
,
2
,
4
,
8
,
9
,
5
,
3
,
6
,
7
};
45
int
post[
9
] = {
8
,
9
,
4
,
5
,
2
,
6
,
7
,
3
,
1
};
46
node *root = buildtree(pre, post,
9
);
47
prints(root);
48
return
0
;
49
}
Data Structure Binary Tree: Construct Full Binary Tree from given preorder and postorder traversals
