题解 | #重建二叉树#

import java.util.*;
public class Solution {
    HashMap<Integer,Integer> map;
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int preLen = pre.length;
        int inLen = in.length;
        if(pre.length != in.length){
            throw new RuntimeException("输入有误！");
        }

        //需要频繁在中序中找到根结点的位置，使用map将数组的遍历查询改为直接查询
        map = new HashMap();
        for(int index = 0; index < in.length; index++){
            map.put(in[index],index);
        }

        return build(pre, 0, preLen-1, in, 0, inLen-1);
    }


    private TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
        //1. 终止条件
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }

        //2. 创建根结点
        TreeNode root = new TreeNode(pre[preStart]);

        //3. 在中序中找到根结点位置，即左右子树的分割界限
        int inindex = map.get(pre[preStart]);

        //4. 在前序中找到左右子树的分割界限:左子树的最后一位元素索引
        int preindex = inindex - inStart + preStart;

        //5. 递归获取左右子树根结点，连接在根结点上
        root.left = build(pre, preStart+1, preindex, in, inStart, inindex-1);
        root.right = build(pre, preindex+1, preEnd, in, inindex+1, inEnd);

        //6. 返回根结点
        return root;
    }
}