给定两个整数数组 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]

解题思路

如下序列， 【3】是根节点

• 前序：【3】, 9, 20, 15, 7
• 中序： 9, 【3】, 15, 20, 7

性质：

1. 前序遍历的第一个元素永远是当前树（或子树）的根节点
2. 在中序遍历中找到这个根节点的位置，那么根节点左边的所有元素属于左子树，根节点右边的所有元素属于右子树

使用 hashMap 预存中序遍历数组，使得后续检索性能优化为O(1)

Java实现

class Solution {

    private Map<Integer,Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd,
                           int[] inorder, int inStart, int inEnd){
        // 如果起始下标大于结束下标，说明没有节点了，返回 null
        if (preStart > preEnd) {
            return null;
        }
        int currVal = preorder[preStart];
        TreeNode currRoot = new TreeNode(currVal);
        // 当前节点在中序数组的下标
        int currInorderIndex = map.get(currVal);
        
        int leftSize = currInorderIndex - inStart;
        // 构建左子树
        currRoot.left = build(preorder, preStart + 1, preStart + leftSize, 
                                  inorder, inStart, currInorderIndex-1);
        // 构建右子树
        currRoot.right = build(preorder, preStart + leftSize + 1, preEnd,
                                  inorder, currInorderIndex+1, inEnd);
        return currRoot;
    }
}