剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树

难度：中等
题目描述

解题思路
这道题之前做过，但是忘得干干净净了。。
现在再做一遍捡一捡，说不定哪次面试就出到了呢
总体思想就是递归，用哈希表来保存对应的中序遍历的下标，空间换时间，免得每次都要去遍历找下标。
然后每次递归的时候，要给对应的左子树和右子树在对应数组里的下标，左端点大于右端点的时候返回空。要注意下标的对应范围，在前序和中序数组里左子树和右子树的长度是一样的，可以计算出对应的下标。

/*
			 * 剑指 Offer 07. 重建二叉树
			 * 2020/7/17
			 */
			 public TreeNode buildTree(int[] preorder, int[] inorder) {
				 int len = preorder.length;
				 if(len == 0)
					 return null;
				 HashMap<Integer, Integer> indexMap = new HashMap<>(len);
				 for (int i = 0; i < inorder.length; i++) {
					indexMap.put(inorder[i], i);
				}
				 return buildHelper(0, 0, len-1, preorder, indexMap);
				 
				 

			    }
			 public TreeNode buildHelper(int preleft,int inleft,int inright,int[] preorder,HashMap<Integer, Integer> indexMap) {
				 if( inleft > inright) {
					 return null;
				 }
				 int rootval = preorder[preleft];
				 int index = indexMap.get(rootval);  //根节点在中序遍历数组中的位置
				 TreeNode root = new TreeNode(rootval);
				 root.left = buildHelper(preleft+1, inleft,index-1, preorder, indexMap);
				 root.right = buildHelper(preleft+index-inleft+1, index+1, inright, preorder, indexMap);
				 
				 return root;
				
			 }