重建二叉树

public class ReConstructBinaryTree {
    // 缓存中序遍历数组每个值对应的索引
    private Map<Integer, Integer> indexForInOrders = new HashMap<>();

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++)
            indexForInOrders.put(in[i], i);
        return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
    }

    /**
     * @param pre 前序遍历顺序
     * @param preL 按照前序遍历，子树的第一个节点索引
     * @param preR 按照前序遍历，子树的最后一个节点索引
     * @param inL  按照中序遍历，子树的第一个节点索引
     * @return
     */
    private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
        if (preL > preR)
            return null;
        //相对每个子树而言，每个前序遍历的节点都是跟节点
        TreeNode root = new TreeNode(pre[preL]);
        //找到中序遍历下这个根节点的索引位置
        int inIndex = indexForInOrders.get(root.val);
        //根据中序遍历的特点（左根右)，根节点的左边就是左子树，左子树的节点个数如下
        int leftTreeSize = inIndex - inL;
        //左半边部分，根据前序遍历的特点（根左右），左子树的根就在当前根节点的下一个节点
        root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
        //右半边部分，根据前序遍历的特点（根左右），右子树的根就在当前根节点加左子树个数后的下一个节点
        root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
        return root;
    }

}