PROBLEM DESCRIPTION
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. (preorder and inorder consist of unique values.) Leetcode
SOLUTION
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
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return reconstructBstHelper(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
}
public TreeNode reconstructBstHelper(int[] preorder, int[] inorder, int ps, int pe, int ins, int ine) {
//Base Condition
if(ps > pe || ins > ine) return null;
int rootVal = preorder[ps];
TreeNode n = new TreeNode(rootVal);
int idx = getIndexOfRootInOrder(inorder, rootVal);
int lengthOfLST = idx-ins;
//LST
n.left = reconstructBstHelper(preorder, inorder, ps+1, ps+lengthOfLST, ins, idx-1);
//RST
n.right = reconstructBstHelper(preorder, inorder, ps+lengthOfLST+1, pe, idx+1, ine);
return n;
}
public int getIndexOfRootInOrder(int[] list, int val){
for(int i=0; i<list.length; i++){
if(list[i] == val) return i;
}
return -1;
}
}