-
Notifications
You must be signed in to change notification settings - Fork 1
/
buildPostorderAndInorder.cpp
58 lines (53 loc) · 1.08 KB
/
buildPostorderAndInorder.cpp
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
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node* left=NULL;
Node* right=NULL;
Node(int x){
data=x;
left=NULL;
right=NULL;
}
};
int search(int inorder[],int start,int end,int x){
for(int i=start;i<=end;i++){
if(inorder[i]==x){
return i;
}
}
return -1;
}
Node* buildTree(int postorder[],int inorder[],int start,int end){
static int idx=4;
if(start>end){
return NULL;
}
int x=postorder[idx];
idx--;
Node* curr=new Node(x);
if(start==end){
return curr;
}
int pos=search(inorder,start,end,x);
curr->right=buildTree(postorder,inorder,pos+1,end);
curr->left=buildTree(postorder,inorder,start,pos-1);
return curr;
}
void InorderPrint(Node* root){
if(root==NULL){
return ;
}
InorderPrint(root->left);
cout<<root->data<<" ";
InorderPrint(root->right);
}
int main(){
int postorder[]={4,2,5,3,1};
int inorder[]={4,2,1,5,3};
//build tree
Node* root=buildTree(postorder,inorder,0,4);
InorderPrint(root);
return 0;
}