题解 | #重建二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型一维数组 
     * @param vinOrder int整型一维数组 
     * @return TreeNode类
     */
    //递归
    Map<Integer,Integer> map = new HashMap();
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        //因为条件vin.length == pre.length只需判断preOrder即可
        if( preOrder == null || preOrder.length<=0){
            return null;
        }
        //用全局HashMap来存vinOrder，方便后面根据值来获得索引
        for (int i = 0;i<vinOrder.length;i++){
            map.put(vinOrder[i],i);
        }
        TreeNode node = f(preOrder,0,preOrder.length-1,vinOrder,0,vinOrder.length-1);
        return node;
    }
    public TreeNode f(int[] preOrder,int h,int f,int[] vinOrder,int h1,int f1){
        if(h>f && h1>f1){
            return null;
        }
        TreeNode root =new TreeNode(preOrder[h]);
        //拿到根的索引值
        int i = map.get(preOrder[h]);
        //2,4,7   4,7,2
        root.left =f(preOrder,h+1,h+(i-h1),vinOrder,h1,i-1);
        //3,5,6,8   5,3,8,6
        root.right =f(preOrder,h+(i-h1)+1,f,vinOrder,i+1,f1);
        return root;
    }
}