Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Analysis
Similar to Construct Binary Tree from Inorder and Postorder Traversal
Code
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder==null || inorder==null || preorder.length!=inorder.length) {return null;}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i=0; i<inorder.length; i++){
map.put(inorder[i],i);
}
return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, map);
}
private TreeNode build(int[] pre, int ps, int pe, int[] in, int is, int ie, HashMap<Integer, Integer> map){
if(ps>pe || is>ie) {return null;}
int ri = map.get(pre[ps]);
TreeNode root = new TreeNode(pre[ps]);
TreeNode left = build(pre, ps+1, ps+ri-is, in, is, ri-1, map);
TreeNode right = build(pre, ps+ri-is+1, pe, in, ri+1, ie, map);
root.left = left;
root.right = right;
return root;
}
}