[数据结构与算法]【LeetCode】105. 从前序与中序遍历序列构造二叉树

class Solution {
    /**
     * 前序[根，[左子树], [右子树]]
     * 中序[[左子树],根,[右子树]]
     */

    //用HashMap来快速定位中序遍历根节点
    Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) {
        //递归出口
        if (pre_left > pre_right) {
            return null;
        }
        //前序遍历的第一个节点就是根节点
        int root = preorder[pre_left];
        //从中序遍历中找出根节点位置
        int in_root = indexMap.get(root);
        //计算左子树长度
        int left_len = in_root - in_left;
        //建立根节点
        TreeNode rootNode = new TreeNode(root);
        //递归建立左子树
        rootNode.left = myBuildTree(preorder, inorder, pre_left + 1, pre_left + left_len, in_left, in_left + left_len - 1);
        //递归建立右子树
        rootNode.right = myBuildTree(preorder, inorder, pre_left + left_len + 1, pre_right, in_root + 1, in_right);
        return rootNode;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        int n = preorder.length;
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}