题解 | #重建二叉树#

思路： 中序序列可以确定当前节点的左右子树，先序序列可以确定一组节点中根节点是哪一个。

因为要频繁的在俩个数组中进行查找，所以使用两个HashMap分别存放先序序列和中序序列，其中key为节点值(题目中说明了节点的值都不同)，value为节点在先序序列和中序序列中的位置。

递归函数Find(),vin[left]--vin[right]表示当前子树所包含的节点，我们需要找到这些节点中哪个节点是当前子树的根节点，就需要在先序序列pre[]中查找，看哪个节点最先出现（也就是在pre[]中索引最小）哪个节点就是根结点，然后在vin[]数组中这个节点的左边就是它的左子树，右边就是它的右子树，再进行递归调用。

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    // 先遍历先序序列 遇到节点之后
    // 在中序编写序列中找它的位置
    Map<Integer,Integer> preMap = new HashMap<>(); // key是节点值，value是该节点在先序序列中的位置
    Map<Integer,Integer> midMap = new HashMap<>();// key是节点值，value是该节点在中序序列中的位置
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int len = pre.length;
        if(len < 1)
            return null;
        for(int i = 0;i<len;i++){
            preMap.put(pre[i],i);
            midMap.put(vin[i],i);
        }
        int mid = midMap.get(pre[0]);
        TreeNode root = new TreeNode(pre[0]);
        root.left = Find(pre,vin,0,mid-1);
        root.right = Find(pre,vin,mid+1,len-1);
        return root;
    }
    public TreeNode Find(int[] pre,int[] vin,int left,int right){
        if(left > right)
            return null;
        if(left == right)
            return new TreeNode(vin[left]);
        TreeNode temp = null;
        int min = right;
        // 寻找left-right中最先在线序序列中出现的节点(在vin中的索引)
        for(int i = left;i<=right;i++){
            min = preMap.get(vin[i])<preMap.get(vin[min])?i:min;
        }
        temp = new TreeNode(vin[min]);
        temp.left = Find(pre,vin,left,min-1);
        temp.right = Find(pre,vin,min+1,right);
        return temp;
    }
}