小米回复我了，白激动一场。。。

最近一网友在投递小米岗位的时候被告知发错信息了，这个有可能是真的发错了，也有可能是招聘关闭了，所以在毕业之前就尽量把工作找好。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第105题：从前序与中序遍历序列构造二叉树。

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

输出: [3,9,20,null,null,15,7]

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

输出: [-1]

public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 为了方便后续进行查找，先把中序数组的所有值存储到map中
    Map<Integer, Integer> map = new HashMap<>();
    int length = inorder.length;
    for (int i = 0; i < length; i++)
        map.put(inorder[i], i);
    return build(preorder, map, 0, 0, length - 1);
}

private TreeNode build(int[] preorder, Map<Integer, Integer> map,
                       int preStart, int inStart, int inEnd) {
    if (inStart > inEnd) return null;// 表示数组被访问完了。
    // 使用前序数组的第一个元素创建根节点
    TreeNode root = new TreeNode(preorder[preStart]);
    // 查找根节点在中序数组中位置
    int index = map.get(root.val);
    int leftCount = index - inStart;// 左子树的所有节点个数
    // 前序数组区间划分：
    // [preStart, preStart]根节点
    // [preStart + 1, preStart + leftCount]左子树
    // [preStart + leftCount + 1, ……]右子树
    // 中序数组区间划分：
    // [inStart, index - 1]左子树
    // [index, index]根节点
    // [index + 1, inEnd]右子树
    root.left = build(preorder, map, preStart + 1, inStart, index - 1);
    root.right = build(preorder, map, preStart + leftCount + 1, index + 1, inEnd);
    return root;
}

public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // 为了方便后续进行查找，先把中序数组的所有值存储到map中
        unordered_map<int, int> m;
        int length = inorder.size();
        for (int i = 0; i < length; i++)
            m[inorder[i]] = i;
        return build(preorder, m, 0, 0, length - 1);
    }

    TreeNode *build(vector<int> &preorder, unordered_map<int, int> &m,
                    int preStart, int inStart, int inEnd) {
        if (inStart > inEnd)
            return nullptr;// 表示数组被访问完了。
        // 使用前序数组的第一个元素创建根节点
        TreeNode *root = new TreeNode(preorder[preStart]);
        // 查找根节点在中序数组中位置
        int index = m[root->val];
        int leftCount = index - inStart;// 左子树的所有节点个数
        // 前序数组区间划分：
        // [preStart, preStart]根节点
        // [preStart + 1, preStart + leftCount]左子树
        // [preStart + leftCount + 1, ……]右子树
        // 中序数组区间划分：
        // [inStart, index - 1]左子树
        // [index, index]根节点
        // [index + 1, inEnd]右子树
        root->left = build(preorder, m, preStart + 1, inStart, index - 1);
        root->right = build(preorder, m, preStart + leftCount + 1, index + 1, inEnd);
        return root;
    }

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    def build(preStart: int, inStart: int, inEnd: int):
        if inStart > inEnd:
            return None  # 表示数组被访问完了。
        # 使用前序数组的第一个元素创建根节点
        root = TreeNode(preorder[preStart])
        # 查找根节点在中序数组中位置
        index = m[root.val]
        leftCount = index - inStart  # 左子树的所有节点个数
        ''' 前序数组区间划分：
        [preStart, preStart]根节点
        [preStart + 1, preStart + leftCount]左子树
        [preStart + leftCount + 1, ……]右子树

        中序数组区间划分：
        [inStart, index - 1]左子树
        [index, index]根节点
        [index + 1, inEnd]右子树
        '''
        root.left = build(preStart + 1, inStart, index - 1)
        root.right = build(preStart + leftCount + 1, index + 1, inEnd)
        return root

    # 为了方便后续进行查找，先把中序数组的所有值存储到map中
    m = {element: i for i, element in enumerate(inorder)}
    return build(0, 0, len(preorder) - 1)