[数据结构与算法]从前中后序遍历构造二叉树，三题无脑秒杀

如果只是前中后序遍历的其中一种，是不可能唯一确定一个二叉树的，必须是其中两个的结合，由此便产生了三道题目，在这里可以全部秒杀。
需要记住的要点是：
前序（根左右）——第一个节点一定是根节点；
中序（左根右）——根节点左边一定是左子树，右边一定是右子树；
后序（左右根）——最后一个节点一定是根节点。

树节点类定义如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder: # 判断空树
            return None
        root = TreeNode(preorder[0])
        i = inorder.index(root.val)
        root.left = self.buildTree(preorder[1:i+1], inorder[:i])
        root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
        return root

从前序找到根节点，然后找到其在中序的位置，区分左右子树，递归。

106. 从中序与后序遍历序列构造二叉树

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder: # 判断空树
            return None
        root = TreeNode(postorder[-1])
        i = inorder.index(root.val)
        root.left = self.buildTree(inorder[:i], postorder[:i])
        root.right = self.buildTree(inorder[i+1:], postorder[i:-1])
        return root

从后序找到根节点，然后找到其在中序的位置，区分左右子树，递归。

889. 根据前序和后序遍历构造二叉树

class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
        if not pre: # 判断空树
            return None
        root = TreeNode(pre[0])
        if len(pre) == 1:  # 下面用到了pre[1]，则必须确保长度大于1
            return root
        i = post.index(pre[1])
        root.left = self.constructFromPrePost(pre[1:i+2], post[:i+1])
        root.right = self.constructFromPrePost(pre[i+2:], post[i+1:-1])
        return root

从前序找到根节点，可知其下一个节点是左子节点（左子树的根节点），在后序中找到其位置，区分左右子树，递归。

总结：三道题的关键，就是从前序或者后序遍历找到根节点，然后使用根节点或者根节点的左子节点来区分左右子树，完成递归。可以注意到，递归的时候：preorder 肯定没有第一个（根节点），inorder肯定没有第 i 个，postorder肯定没有最后一个；然后根据区分左右子树时用的是根节点还是它的左子节点，决定是 i 还是 i + 1。