题目链接给的是889，而105和106请自行直接检索。

1.前序 + 中序
前序+中序可以构造唯一的二叉树，我们向build传递三个参数
第一个参数是根节点在前序遍历中的下标值
第二和第三个参数是以root为根的树在中序遍历中的下标值范围，第二个参数是范围的左端，第三个参数是范围的右端
在build中，初始化了当前root后，其左子树可以基于build(root+1,left,i-1)构造
其中，root+1就是左子树的根在前序遍历中的下标。而i呢，就是在中序遍历中的值下标，自然left~i-1就是root的左子树范围了。当前root的右子树也是一样的。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def build(root,left,right):
            if left > right :
                return None
            node = TreeNode(val=preorder[root])
            i =  mapper[preorder[root]]
            # left tree : left - i-1
            node.left = build(root+1,left,i-1)
            # right tree : i+1 - right
            node.right = build(root+i-left+1,i+1,right)     
            return node   
        mapper = defaultdict(int)
        for i , x in enumerate(inorder) :
            mapper[x] = i 
        return build(0 , 0 , len(inorder)-1)

2.中序+后序
中序+后序也可以构造一个唯一的二叉树。代码模板和上面的差不多。
我们仍以中序的范围作为第二和第三参数。第一参数是root在后序遍历中的范围。
上一题我忘说了，在递归的时候，两个build中的第一个参数，也就是新root是怎么算的。
这简单啊，后序遍历中，末尾是root，次末尾位置就是右子树的root。
那么左子树的root呢？这需要你知道右子树范围的长度，也就是i+1~right这么大的范围，长度自然就是right-i。所以左子树的根在前序中的下标就是root-1-right+i(root-1是右子树的根在前序中的下标，那么root-1-x=right-i,其中x是左子树的根的下标)

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

        def build(root , left , right) :
            if left > right :
                return None
            node = TreeNode(val=postorder[root])
            i = mapper[postorder[root]]
            # left root : root-1-right+i 
            node.left = build(root-1-right+i,left,i-1) 
            # right root : root-1
            node.right = build(root-1,i+1,right)
            return node

        mapper = defaultdict(int)
        for i , x in enumerate(inorder) :
            mapper[x] = i 
        return build(len(postorder)-1,0,len(inorder)-1) 

3.前序+后序
前序+后序无法构造唯一的二叉树，虽然答案不唯一但想构造一个满足题意的还是没问题的。代码模板仍然可以套用前面两个题的。
不同的地方在于，前面通过中序遍历，直接唯一地划分了以root为中心，左右子树非常明了。
这里不同了，我们没有中序遍历，所以左右子树不唯一，我们只需要找到一个合理的左子树和右子树就行。
这里我们将第一参数定为root在前序中的下标，那么第二和第三参数是该树在后序中的下标范围。
在build中，你初始化了当前root后，需要对比两个序列，在前序遍历中，从root+1开始向后看，在后序遍历中，从left开始向后看，两个序列都同时向后看相同的长度，如果他们出现的数字集合一致，说明找到了一个合法的左子树。
然后你就可以如法炮制build当前root的左右子树了。
注意，由于题目规模，你可以使用一个int当成set存储数字出现的情况，直接用int和int比较，而不用set比较，但我操作下来发现效率相对没有变快。

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

        def build(root, left , right) :
            if left > right :
                return None 
            node = TreeNode(val=preorder[root]) 
            # 需要定出左子树的长度
            idx = 0
            for i in range(1,right) :
                if set(preorder[root+1:root+1+i]) == set(postorder[left:left+i]) :
                    idx = i
                    break 
            node.left = build(root+1, left , left + idx - 1 )
            node.right = build( root + idx + 1, left + idx , right-1)
            return node 

        return build(0,0,len(postorder)-1)