二叉树作为数据结构中一种简单而且重要的数据结构，他的存储结构和算法都相对比较简单，因此他也显得特别重要，因为很多问题都可以抽象为二叉树的问题。

在这里我们对于二叉树的基本概念不做详细介绍，我们这里主要介绍二叉树的前序遍历，中序遍历，和后序遍历三种问题和如何通过他的前序遍历，中序遍历，后序遍历构造相应的二叉搜索树的问题。

在这之前，我们先简单了解一下二叉树的三种遍历到底是什么样子的。

我的记忆方式为：

                                       前序遍历-DLR（根节点，左子树，右子树）

                                       中序遍历-LDR（左子树，根节点，右子树）

                                       后序遍历-LRD（左子树，右子树，根节点）

下面我们举例子：

                                              

前序遍历的结果：num1 = [1 , 2 , 4 , 5 , 3 , 6 , 7]

中序遍历的结果：num2 = [4 , 2 , 5 , 1 , 6 , 3 , 7]

后序遍历的结果：num3 = [4 , 5 , 2 , 6 , 7 , 3 , 1]

这是三种遍历的结果，在这个结果中，我们发现，对于前序遍历的结果来说，二叉树的根节点为前序遍历数组的第一个值，即num1[0]，后序遍历的最后一个值，即为num3[-1]。这是个很重要的信息，这对于我们根据一个二叉树他的前序遍历，中序遍历，后序遍历构造构造二叉搜索树具有非常大的帮助。

因为如果我们要构造二叉搜索树，首先是要确定根节点的位置，在确定根节点的位置之后，我们再确定左右子树的大小和长度。干说显得比较枯燥，下面我们举例论证一下。

1008. 前序遍历构造二叉搜索树

难度中等205收藏分享切换为英文接收动态反馈

给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

示例 1：

输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

示例 2:

输入: preorder = [1,3]
输出: [1,null,3]

提示：

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• preorder 中的值 互不相同

题目思路：

我们可以得到，前序遍历结果的首字母为数的根，因此我们首先root_val = preorder[0]得到二叉搜索树的根，且由题意可知二叉树右子树的值大于左子树，因此我们遍历前序遍历的数组可以得到左子树的内容和右子树的内容，之后分别打入递归即可。

Python代码： 

# 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

 

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

难度中等233收藏分享切换为英文接收动态反馈

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示：

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

题目思路：

前序遍历的首位即为根节点，后续遍历的末尾为根节点，
前序遍历的结果为（根节点，左子树，右子树）
后续遍历的结果为（左子树，右子树，根节点）
依照这个思想，我们进行求解，首先root = TreeNode(preorder[0]) 确定根节点的位置，然后在后续
在后续遍历中 a_left = postorder.index(preorder[1])找到
左子树根节点的位置，可以得到左子树的范围postorder_left = postorder[:a_left+1] ，因为左子树的长度是固定的
可以同理得到前序遍历中左子树的范围preorder_left = preorder[1:a_left+2]
同理，右子树的范围也可以得到，递归得到全部的root。

Python代码： 

# 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

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

难度中等1516收藏分享切换为英文接收动态反馈

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

题目思路： 

前序遍历【根节点，左子树，右子树】
中序遍历【左子树，根节点，右子树】参考这个求解即可
在前序遍历中root_val = preorder[0] 确定根节点的位置，在中序遍历中找到根节点的位置，中序遍历中根节点左边的即为左子树的范围
右边的即为右子树的范围，因为左子树右子树的长度是固定的，因此我们可以在中序遍历中也确定左右子树的范围
打入递归即可

Python代码:

# 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

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

难度中等709收藏分享切换为英文接收动态反馈

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

解题思路： 

中序遍历为【左子树，根节点，右子树】
后序遍历为【左子树，右子树，根节点】
后序遍历的最有一个值为根节点，在中序遍历中找到根节点的位置，中序遍历中根节点左边的为左子树的长度，右边的为右子树的长度
，左右子树的长度一定，因此我们也可以在后序遍历中确定左右子树，打入递

Python代码：

# 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

449. 序列化和反序列化二叉搜索树

难度中等280收藏分享切换为英文接收动态反馈

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1：

输入：root = [2,1,3]
输出：[2,1,3]

示例 2：

输入：root = []
输出：[]

提示：

• 树中节点数范围是 [0, 104]
• 0 <= Node.val <= 104
• 题目数据 保证 输入的树是一棵二叉搜索树。

通过次数22,273提交次数38,572

解题思路：先后序遍历得到数组，使用map函数变成字符串，然后再使用map函数变成列表，进行后序遍历构造二叉搜索树。

# 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 
            serialize_1(root.left)
            serialize_1(root.right)
            ans.append(root.val)
        serialize_1(root)
        return ' '.join(map(str , ans))#然后使用map函数，变成字符串

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        ads = list(map(int , data.split()))#使用map函数，拆看，变成列表
        def deserialize_1(ads): #后序遍历构造二叉搜索树
            if not ads: return None
            val = ads.pop()
            ads_right = []
            ads_left = []
            root = TreeNode(val)
            for i in range(len(ads)):
                if ads[i]>val: ads_right.append(ads[i])
                elif ads[i]<val: ads_left.append(ads[i])
            root.left = deserialize_1(ads_left)
            root.right = deserialize_1(ads_right)
            return root
        return deserialize_1(ads)