题解 | #重建二叉树#

import java.util.Arrays;
import java.util.*;
public class Solution {
    static Map<Integer,Integer> map;
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0||in.length==0)return null;
        map=new HashMap<Integer,Integer>();
        int n=in.length;
        for(int i=0;i<n;i++){
            map.put(in[i],i);
        }
        TreeNode root=solveHelp(pre,0,n-1,in,0,n-1);
        return root;
    }
    // 构建树
    public static TreeNode solveHelp (int[] xianxu,int preLeft,int preRight,int[] zhongxu,int inLeft,int inRight) {
    	if(preLeft>preRight)return null;
        int in_root=map.get(xianxu[preLeft]);
        int left_nums=in_root-inLeft;
        TreeNode root=new TreeNode(xianxu[preLeft]);
        root.left=solveHelp(xianxu,preLeft+1,left_nums+preLeft,zhongxu,inLeft,in_root-1);
        root.right=solveHelp(xianxu,left_nums+preLeft+1,preRight,zhongxu,in_root+1,inRight);
        return root;
    }
}