-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBinary Trees2-Construct Tree Using Inorder and PostOrder
78 lines (66 loc) · 2.4 KB
/
Binary Trees2-Construct Tree Using Inorder and PostOrder
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
For a given postorder and inorder traversal of a Binary Tree of type integer stored in an array/list, create the binary tree using the given two arrays/lists. You just need to construct the tree and return the root.
Note:
Assume that the Binary Tree contains only unique elements.
Input Format:
The first line of input contains an integer N denoting the size of the list/array. It can also be said that N is the total number of nodes the binary tree would have.
The second line of input contains N integers, all separated by a single space. It represents the Postorder-traversal of the binary tree.
The third line of input contains N integers, all separated by a single space. It represents the inorder-traversal of the binary tree.
Output Format:
The given input tree will be printed in a level order fashion where each level will be printed on a new line.
Elements on every level will be printed in a linear fashion. A single space will separate them.
Constraints:
1 <= N <= 10^4
Where N is the total number of nodes in the binary tree.
Time Limit: 1 sec
Sample Input 1:
7
4 5 2 6 7 3 1
4 2 5 1 6 3 7
Sample Output 1:
1
2 3
4 5 6 7
Sample Input 2:
6
2 9 3 6 10 5
2 6 3 9 5 10
Sample Output 2:
5
6 10
2 3
9
***********************************************Code*******************************************
public static BinaryTreeNode<Integer> buildTree(int[] postOrder, int[] inOrder) {
BinaryTreeNode<Integer> root=buildTree(postOrder, inOrder, 0, postOrder.length-1, 0,inOrder.length-1);
return root;
}
private static BinaryTreeNode<Integer> buildTree(int[] postOrder, int[] inOrder, int sPost, int ePost, int sIn, int eIn)
{
if(sPost>ePost)
return null;
int rootData=postOrder[ePost];
BinaryTreeNode<Integer> root=new BinaryTreeNode<Integer>(rootData);
int rootIndex=-1;
for(int i=sIn; i<=eIn;i++)
{
if(rootData==inOrder[i])
{
rootIndex=i;
break;
}
}
int sInLeft=sIn;
int eInLeft=rootIndex-1;
int sPostLeft=sPost;
int leftSubTree= eInLeft-sInLeft+1;
int ePostLeft=(sPostLeft)+(leftSubTree-1);
int sInRight=rootIndex+1;
int eInRight=eIn;
int sPostRight=ePostLeft+1;
int ePostRight=ePost-1;
BinaryTreeNode<Integer> rightChild=buildTree(postOrder,inOrder, sPostRight,ePostRight,sInRight,eInRight);
BinaryTreeNode<Integer> leftChild=buildTree(postOrder,inOrder, sPostLeft, ePostLeft, sInLeft, eInLeft);
root.left=leftChild;
root.right=rightChild;
return root;
}