Problem
Construct a tree from pre-order and in-order traversal arrays.What I learnt here? - Arrays.copyOfRange(int[], int start, int end) copies from start (included) till end-1 (i.e. exclusive of end)
Solution
import java.util.Arrays;
public class TreeProblem2 {
class Tree {
int node;
Tree left;
Tree right;
}
int preIndex = 0;
Tree construct(int[] pre, int[] in) {
if(preIndex >= pre.length || in.length==0) return null;
Tree t= new Tree();
t.node = pre[preIndex++]; //first element in preorder is the root
//Get pos of root in the inorder.
//Elements left of that will be the left tree
//Elements to the right of that will be the right tree
int i =0;
for(;i< in.length; i++){
if(in[i] == t.node) break;
}
int[] leftIn = Arrays.copyOfRange(in, 0, i);
int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);
t.left = construct(pre, leftIn);
t.right = construct(pre, rightIn);
return t;
}
public static void main(String[] args) {
int[] pre = {10,5,80,9,2,6};
int[] in = {80,5,9,10,6,2};
TreeProblem2 ob = new TreeProblem2();
Tree t = ob.construct(pre, in);
TreeOperations.printTree(t);
}
}
No comments:
Post a Comment