输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3 / 9 20 / 15 7
限制：
0 <= 节点个数 <= 5000
题解：
递归方式 先根据先序遍历确认根节点，然后找出根节点在中序遍历的位置，从而确定左子树的长度和右子树的长度，对应到先序遍历中也能找出对应的左子树和右子树， 分别递归左子树和右子树，重复上面步骤。
例如：
上面示例所示：
第一次递归：
由先序遍历知：3为根节点，
由中序遍历知，左子树有1个，为9；右子树有3个，为15,20,7
第二次递归：
左子树递归：
先序遍历中，左子树为9，由此，根节点为9
因为中序遍历中9也是根节点。
由此，确认9为跟节点。
右子树遍历：
先序遍历中，右子树为20,15,7，由此，20为根节点。
中序遍历中，则找到20的根节点，则左子树为15，右子树为7.
代码：
代码语言：javascript复制public class offer07 {
private static Map<Integer,Integer> indexMap;
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] preorder = new int[]{3,9,20,15,7};
int[] inorder = new int[]{9,3,15,20,7};
TreeNode tree = buildTree(preorder,inorder);
System.out.println(tree);
}
/**
* 思路：主要是递归的定位到根节点
* @param preorder
* @param inorder
* @return
*/
public static TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
//构造哈希映射，帮助我们快速定位根节点
indexMap = new HashMap<Integer,Integer>();
for(int i=0;i<n;i ){
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder,inorder,0,n-1,0,n-1);
}
/**
* 递归方式
* 先根据先序遍历确认根节点，然后找出根节点在中序遍历的位置，从而确定左子树的长度和右子树的长度，对应到先序遍历中也能找出对应的左子树和右子树，
* 分别递归左子树和右子树，重复上面步骤。
*
* @param preorder
* @param inorder
* @param preorder_left
* @param preorder_right
* @param inorder_left
* @param inorder_right
* @return
*/
public static TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
if(preorder_left>preorder_right){
return null;
}
//前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
//在中序遍历中定位根节点
int inorder_root = indexMap.get(preorder[preorder_root]);
//先把根节点建立出来
TreeNode root = new TreeNode(preorder[preorder_root]);
//得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
//递归的构造左子树，并连接到根节点
//先序遍历中【从左边界 1 开始的size_left_subtree】个元素就对应了中序遍历中【从左边界开始到根节点定位-1】的元素
root.left = myBuildTree(preorder,inorder,preorder_left 1,preorder_left size_left_subtree,inorder_left,inorder_root-1);
//递归的构造右子树，并连接到根节点
//先序遍历中【 从左边界 1 左子树节点数目 对应 开始 到右边界】的元素对应了中序遍历中 【从左边界开始 到 根节点-1】的元素
root.right = myBuildTree(preorder,inorder,preorder_left size_left_subtree 1,preorder_right,inorder_root 1,inorder_right);
return root;
}
}
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
