[leetcode]Construct Binary Tree from Preorder and Inorder Traversal

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public class Solution { HashMap<Integer, Integer> lookup = new HashMap<Integer, Integer>(); public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0) return null; for (int i = 0; i < inorder.length; i++){ lookup.put(inorder[i], i); } return buildTreeRec(0, preorder.length-1, 0, inorder.length-1, preorder); } private TreeNode buildTreeRec(int preStart, int preEnd, int inStart, int inEnd, int[]preorder){ if (preStart > preEnd) return null; int index = lookup.get(preorder[preStart]); TreeNode root = new TreeNode(preorder[preStart]); root.left = buildTreeRec(preStart+1, preStart+(index-inStart), inStart, index-1, preorder); root.right = buildTreeRec(preStart+index-inStart+1, preEnd, index+1, inEnd, preorder); return root; } }