打卡题目：leetcode第105题，从前序与中序遍历序列构造二叉树
    相似题目：106、889、1008
    注意：根据前序+中序可以构建唯一的二叉树；根据中序+后序可以构建唯一的二叉树。但是，根据前序+后序不能构建唯一的二叉树！
    image.png

    【思路】
    首先回顾遍历的顺序：前序遍历是根节点-左子树-右子树，中序遍历是左子树-根节点-右子树。
    那么前序遍历数组的第一个元素肯定是根节点，在中序遍历数组中找到这个元素，则其前一部分是左子树的元素，其后一部分是右子树的元素。递归即可求解。
    注意：前序遍历+后序遍历，不能确定唯一的二叉树！

    【代码】

    1. # Definition for a binary tree node.
    2. # class TreeNode:
    3. #     def __init__(self, x):
    4. #         self.val = x
    5. #         self.left = None
    6. #         self.right = None
    8. class Solution:
    9.     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    10.         # 前序遍历，第一个是head
    11.         # 中序遍历，前一部分是左子树，后一部分是右子树
    12.         if len(preorder) == 0:
    13.             return None
    14.         node = TreeNode(preorder[0])
    15.         index = inorder.index(preorder[0])
    16.         node.left = self.buildTree(preorder[1:index+1], inorder[:index])
    17.         node.right = self.buildTree(preorder[index+1:], inorder[index+1:])
    18.         return node