LC 105从前序与中序遍历序列构造二叉树Construct Binary Tree from Preorder and Inorder Traversal　中等

依据先序与中序遍历数组重建二叉树（节点值互不相同）。

思路 哈希中序位置递归：先序首元素为根，查中序分界拆左右，指针消费先序。时间 O(n)。

class Solution:
    def buildTree(self, preorder, inorder):
        idx = {v: i for i, v in enumerate(inorder)}
        pre = 0

        def build(lo, hi):
            nonlocal pre
            if lo > hi:
                return None
            root = TreeNode(preorder[pre])
            pre += 1
            mid = idx[root.val]
            root.left = build(lo, mid - 1)
            root.right = build(mid + 1, hi)
            return root
        return build(0, len(inorder) - 1)