题解 | #重建二叉树#

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> map = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre==null||vin==null||pre.length!=vin.length){
            return null;
        }
        int len=pre.length;
        for(int i=0;i<len;i++){
            map.put(vin[i],i);
        }
        return reBuildBinTree(pre,vin,0,len-1,0,len-1);
    }
    public TreeNode reBuildBinTree(int[] pre,int[] vin,int pL,int pR,int vL,int vR){
        if(pL>pR||vL>vR){
            return null;
        }
        int index=map.get(pre[pL]);
        TreeNode root=new TreeNode(pre[pL]);
        root.left=reBuildBinTree(pre,vin,pL+1,pL+index-vL,vL,index-1);
        root.right=reBuildBinTree(pre,vin,pL+index-vL+1,pR,index+1,vR);
        return root;
    }
}