二叉树的前序遍历，中序遍历，后序遍历-详解-配套例题

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        if not preorder: #当为空的时候，我们输出none
            return None
        root_val = preorder[0]  #前序遍历结果的首位为二叉树的前节点
        root = TreeNode(root_val)
        preorder_left = [] #构造两个数组，分别用于存放左子树和右子树的结果
        preorder_right = []
        for i in range(1 , len(preorder)):
           if  preorder[i] < root_val:       #如果找到小于root_val, 则为左子树的内容，存入左子树
                preorder_left.append(preorder[i])
           else:                             #如果找到大于root_val,则为右子树的内容，存入右子树
                preorder_right.append(preorder[i])
        root.left = self.bstFromPreorder(preorder_left)   #开始递归，左子树的往树的左边递归
        root.right = self.bstFromPreorder(preorder_right)  #右子树，往树的右边递归
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
        if not preorder or not postorder:
            return None
        root = TreeNode(preorder[0])     #前序遍历的首位即为二叉树的根
        if len(preorder) == 1:   #如果为1，即为根输出即可
            return root
        a_left = postorder.index(preorder[1]) #在后序遍历中找到左子树的根节点 
        preorder_left = preorder[1:a_left+2] # 那么左子树的范围为，
        preorder_right = preorder[a_left+2:]  #右子树的范围
        postorder_left = postorder[:a_left+1] #左子树的范围
        postorder_right = postorder[a_left+1:len(postorder)-1] #右子树的范围
        root.left = self.constructFromPrePost(preorder_left , postorder_left)  #分别进行递归
        root.right = self.constructFromPrePost(preorder_right , postorder_right)
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        root_val = preorder[0]  #前序遍历的首节点为根节点
        root = TreeNode(root_val)
        mid = inorder.index(root_val) #在中序遍历中找到根节点的位置
        inorder_left = inorder[:mid]  #中序遍历中根节点左边的即为左子树的范围
        inorder_right = inorder[mid+1:] #右边的即为右子树的范围
        preorder_left = preorder[1:len(inorder_left)+1]#因为左子树右子树的长度是固定的，因此我们可以在中序遍历中也确定左右子树的范围
        preorder_right = preorder[len(inorder_left)+1:]
        root.left = self.buildTree(preorder_left , inorder_left)#打入递归即可
        root.right = self.buildTree(preorder_right , inorder_right)
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder: 
            return None
        val = postorder[-1]  # 后序遍历的最有一个值为根节点
        root = TreeNode(val) # 
        mid = inorder.index(val)  #在中序遍历中找到根节点的位置
        inorder_left = inorder[:mid] #中序遍历中根节点左边的为左子树的长度，右边的为右子树的长度
        inorder_right = inorder[mid+1:]
        postorder_left = postorder[:len(inorder_left)]  #左右子树的长度一定，因此我们也可以在后序遍历中确定左右子树
        postorder_right = postorder[len(inorder_left):len(postorder)-1]
        root.left = self.buildTree(inorder_left , postorder_left)#打入递归
        root.right = self.buildTree(inorder_right , postorder_right)
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Codec:
    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        ans = []
        def serialize_1(root):#后序遍历，构造数组，进行所谓的序列化
            if not root: return