-
Notifications
You must be signed in to change notification settings - Fork 0
/
Binary Trees2-Construct Tree Using Inorder and Preorder
79 lines (66 loc) · 2.46 KB
/
Binary Trees2-Construct Tree Using Inorder and Preorder
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
79
For a given preorder 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 preorder-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
1 2 4 5 3 6 7
4 2 5 1 6 3 7
Sample Output 1:
1
2 3
4 5 6 7
Sample Input 2:
6
5 6 2 3 9 10
2 6 3 9 5 10
Sample Output 2:
5
6 10
2 3
9
******************************************Code********************************************
public static BinaryTreeNode<Integer> buildTree(int[] preOrder, int[] inOrder) {
BinaryTreeNode<Integer> root= buildTree(preOrder, inOrder,0,preOrder.length-1,0,inOrder.length-1);
return root;
}
private static BinaryTreeNode<Integer> buildTree(int[] preOrder,int[] inOrder, int sPre, int ePre, int sIn, int eIn)
{
if(sPre>ePre)
return null;
int rootData = preOrder[sPre];
BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(rootData);
int rootInorder = -1;
for (int i = sIn; i <= eIn; i++)
{
if (rootData == inOrder[i])
{
rootInorder = i;
break;
}
}
int sInLeft = sIn;
int eInLeft = rootInorder - 1;
int sPreLeft = sPre + 1;
int leftSubTreeLength = eInLeft - sInLeft + 1;
int ePreLeft = (sPreLeft) + (leftSubTreeLength - 1);
int sInRight = rootInorder + 1;
int eInRight = eIn;
int sPreRight = ePreLeft + 1;
int ePreRight = ePre;
BinaryTreeNode<Integer> leftChild = buildTree(preOrder, inOrder, sPreLeft, ePreLeft, sInLeft, eInLeft);
BinaryTreeNode<Integer> rightChild = buildTree(preOrder, inOrder, sPreRight, ePreRight, sInRight, eInRight);
root.left = leftChild;
root.right = rightChild;
return root;
}