从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

class Solution {
    // 哈希表，用于存储中序遍历数组中每个节点值对应的索引
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    // 主方法：根据前序遍历和中序遍历数组构建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 将中序遍历数组中的值和索引存入哈希表中
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }

        // 调用递归方法构建二叉树
        return build(preorder, 0, preorder.length - 1, 
                     inorder, 0, inorder.length - 1);
    }

    /**
     * 递归方法：根据前序遍历和中序遍历数组构建二叉树
     * @param preorder 前序遍历数组
     * @param preStart 前序遍历数组的起始索引
     * @param preEnd 前序遍历数组的结束索引
     * @param inorder 中序遍历数组
     * @param inStart 中序遍历数组的起始索引
     * @param inEnd 中序遍历数组的结束索引
     * @return 构建的二叉树的根节点
     */
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] inorder, int inStart, int inEnd) {
        // 若起始索引大于结束索引，说明子树为空，返回null
        if (preStart > preEnd) {
            return null;
        }

        // 根节点的值为前序遍历数组的第一个值
        int rootVal = preorder[preStart];
        // 获取根节点在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 创建根节点
        TreeNode root = new TreeNode(rootVal);

        // 左子树节点数目
        int leftSize = index - inStart;

        // 递归构建左子树
        // preStart + 1 是左子树在前序遍历数组中的起始索引
        // preStart + leftSize 是左子树在前序遍历数组中的结束索引
        // inStart 是左子树在中序遍历数组中的起始索引
        // index - 1 是左子树在中序遍历数组中的结束索引
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                          inorder, inStart, index - 1);

        // 递归构建右子树
        // preStart + leftSize + 1 是右子树在前序遍历数组中的起始索引
        // preEnd 是右子树在前序遍历数组中的结束索引
        // index + 1 是右子树在中序遍历数组中的起始索引
        // inEnd 是右子树在中序遍历数组中的结束索引
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                           inorder, index + 1, inEnd);

        // 返回根节点
        return root;
    }
}