怎么构建二叉排序树,怎样构造二叉排序树
引言在上一篇博客《[面试算法]Python实现二叉树三种遍历的递归与非递归形式》中，我们详细讨论了二叉树深度优先遍历的各种方式。一个常见的面试问题是，如何根据三种遍历的结果恢复一棵二叉树或者重建它？还是以上一篇博客的二叉树为例。二叉树的示意图及其三次遍历的结果如下所示：
首先，二叉树是否可以根据某次遍历的结果恢复？比如我们只知道A是二叉树的根节点，其他的我们都不知道。例如，下面的二叉树与上面的二叉树具有相同的前序遍历结果：
因此，仅仅根据前序遍历的结果来恢复唯一二叉树是不可能的。根据中序遍历的结果，我们什么都不知道，因为D B G E A C F可能对应这样一个二叉树：D (B G E A C F)，其中D为根节点，左子树为空，(B G E A C F)为右子树，也满足上述中序遍历的结果。根据后序遍历，二叉树不能唯一恢复。根据D G E B F C A的后序遍历，我们只能知道A是根节点，其他的就不知道了。因此，我们至少需要两个遍历结果才能重建二叉树。
如果有了前序遍历和后序遍历的结果，是否可以恢复唯一二叉树？不能。
给定前序遍历结果A B D E G C F和后续遍历结果D G E B F C A，可以看出A是根节点，所以去掉A后分别是B D E G C F和D G E B F C。在这两个序列中，前者的第一个元素B不等于后者的最后一个元素C，说明这两个前序遍历和后序遍历属于两个子树，而不是一个。
让我们来看看：
前言：英国D E G C F
按顺序排列：D
可以肯定的是，B是一个子树的根节点，C是另一个子树的根节点。逐一扫描，发现B D E G和D G E B应该属于一个子树，因为在这两个序列中：前者的第一个元素=后者的最后一个元素，这符合前序和后序遍历的特点。同样，C F和F C属于同一个子树。而B D E G应该属于左子树，因为在前序遍历中这个序列在C F之前。看到这里，我觉得有点希望二叉树可以恢复，但是现在问题来了。
既然C F和F C是根节点A的右子树的前中序遍历结果，那么这个子树中的C一定是根节点，那么F节点是属于左子树还是右子树呢？如果f是右子树，那么左子树是空的，符合前序和中序的遍历结果，也和原二叉树一样。如果F属于左子树，也符合前序和中序的遍历结果。在这一点上，存在无法唯一确定的问题，在B D E G C F中也存在类似的问题。
所以二叉树不能根据一阶和二阶的遍历结果来重构。只剩下两种可能：前序中的中序和后序中的中序，这两种都可以用于二叉树重构。
根据前序遍历，中序遍历减少二叉树。根据前序遍历结果A B D E G C F和中序遍历结果D B G E A C F可以看出，A是根节点，而在中序遍历中，根节点可以划分左右子树，也就是说D B G E在中序遍历中是左子树，C F是右子树。无论哪种遍历，一个子树的节点数总是相等的，所以根据左边子树的中序遍历，我们可以把这个子树分成b d的一阶遍历结果例如右边子树是相似的。
因此：
左子树前中序的结果是：B D E G和d b g e。
右边子树前中序的结果是：c f和C F。
剩下的事情就是采用同样的方法。
我们先看左边的子树。根据B D E G的前序遍历，B一定是根节点。如果放在中序遍历，可以看到左右子树分别是D和G E，所以B的左子树对应的是前序和中序：D和D的结果，只有一个节点，左子树的重构就完成了B的右子树对应于前序和m的结果
对于右侧子树的前后顺序：C F和C F，可以看出C是根节点，F属于右侧子树，右侧子树只有一个F节点，左侧子树为空。重建完成！
上述过程是递归的，所以可以用递归程序来完成。递归的方法是：
根据前序遍历确定根节点根，根据根在中序遍历中的位置划分左右子树对应的中序遍历结果；根据左右子树顺序遍历的节点个数信息，结合前序遍历，确定左右子树的前序遍历结果；现在知道了左子树的前中序，就可以递归了；你也知道右边子树的前中序，可以递归；递归边界：如果一个子树的节点数为0，则重新构建该子树，其根节点为空，触及递归边界。通过根据前面的顺序遍历中间的顺序来减少二叉树的Python代码如下：
#全局变量记录遍历结果的结果=[]#前言defdfs _ before (root):如果root==None: #遇到None，说明不需要继续搜索。返回结果。append(root)DFS _ before(root . left)DFS _ before(root . right)#按中间顺序遍历def dfs_middle(root)。if root==none:return DFS _ middle(root . left)result . append(root . Right)# Traverse def DFS _ after(root):if root==none:return DFS _ after(root . left)DFS _ after(root . Right)result . append(root)# node的数据结构# val表示值，left表示当前节点的左子节点的地址，Class node(object):def _ _ Right _ _(self，val，left，Right): self。val=valself。left=leftself。right=right #前中序二叉树# arr1:前序遍历结果# arr2:中序遍历结果def before_middle_bintree(arr1，Arr2): if len(arr1)==0: #递归边界：如果一个子树为空，则直接返回该子树的根节点：empty返回None else: root=arr1[0] #根据前序遍历的结果可知，根节点root_location=-1 for i， Inenumerate (arr2): #查找根节点在中序遍历结果数组中的位置if root==x:root _ location=I break #截中序遍历left _ arr 2=arr 2[0:root _ location]#左子树的中序遍历结果right _ arr 2=arr 2[root _ location 1:]#右子树的中序遍历结果#查找左右子树的长度num _ left=len (left _ arr2) num _ right=len (right _ arr2) #根据左右子树的长度，求前序遍历结果left_arr1=arr1[1:1 num_left] #左子树的前序遍历结果(要去掉根节点，所以从1开始)right_arr1=arr1[1 num_left:] #右子树的前序遍历结果(从左子树的最后一个元素开始)left _ root=before _ middle _ bintree(left _ arr 1， left _ arr2) #递归重建左子树，返回左子树根节点Right _ root=before _ middle _ bin tree(Right _ arr 1，right _ arr2) #递归重建右子树并返回右子树根节点返回节点(root，left_root，Right_root) #重建整个树if _ _ name _ _= _ _ main _ :# node7=Node( g ，none，none) # node5=node (e ，Node 7， 无)# node4=node (d ，none，none) # node2=Node(B ，node4，node5) # node6=Node(F ，None，None) # node3=Node(C ，None，node6) # node1=Node(A ，node2， 3)# DFS _ before(node 1)# DFS _ Middle(node 1)# DFS _ after(node 1)# print([x . val for x in result])#前中序二叉树arr1=[a ， b ， d ， e ， g ]#前序遍历结果arr2=[d ， b ， g ， e ， a ， c ， F] #中序遍历结果root=before _ Middle _ bintree(arr 1，Arr2) #重建DFS _ before (root
[A ， B ， D ， E ， G ， C ， F] [D ， B ， G ， E ， A ， C ， F]进程以退出代码0结束，如下所示
给定逆序遍历结果D G E B F C A和中序遍历结果D B G E A C F，从逆序遍历结果可以看出，A是根节点，而在中序遍历中，根节点可以分为左右两个子树，说明在中序遍历中D B G E是左子树，C F是右子树。所以左子树对应的中序遍历结果是：D B G E，右子树对应的中序遍历结果是：C F .所以左子树对应的后续遍历元素个数也是4，所以一定是D G E B C F: D G E B .的前四个元素而右子树对应的后续遍历结果是：F C
先看左边的子树，然后按中间顺序遍历D G E B和D B G E。所以B是根节点，它的左子树是D，它的右子树是G E，B的左子树D只有一个元素，重构结束。B的右子树的逆序和中序分别是G E和G E。根据逆序遍历，我们知道E是根节点，G是左子树，重构完成。这样，左子树的重建就结束了。
看右边的子树，按倒序遍历F C和C F。按照逆序遍历，根节点为C，按照中序遍历，右子树为F，重构完成。
综上所述，递归的过程如下：
根据后续遍历的结果，最后一个元素是根节点；在中序遍历中找到根节点的位置，划分左右子树，确定左右子树对应的中序遍历结果；根据左右子树中顺序遍历的结果(遍历方式不同，节点个数总是相等)，确定左右子树中顺序遍历的结果；分别递归重建左右子树；递归边界是：当一个子树中的节点数为空时，触及递归边界。通过以逆序遍历中间顺序来简化二叉树的Python代码如下：
# 全局变量记录遍历的结果结果=[]#前序def dfs_before(根):如果root==None: #遇到没有，说明不用继续搜索下去返回结果。追加(根)DFS _ before(根。左)DFS _ before(root。右)#中序遍历def DFS _ middle(root):如果root==None:返回DFS _ middle(根。左)结果。append(root)DFS _ middle(root。右)#后序遍历def DFS _ after(root):如果root==None:返回DFS _ after(root。左)DFS _ after(root。右)结果。追加(根)#节点的数据结构# val表示值、左侧表示当前节点的左子节点地址，对表示右子节点地址类节点（对象):def __init__(self，val，left，right):self。val=val自我。左=左我。右=右#后序中序重建二叉树# arr1:后序遍历# arr2:中序遍历def after_middle_bintree(arr1，arr 2):if len(arr 1)==0:return None else:root=arr 1[-1]root _ location=-1 #找到根节点在中序遍历中的位置对我来说， x in enumerate(arr 2):if x==root:root _ location=I break left _ arr 2=arr 2[0:root _ location]#左子树的中序遍历结果右_数组2=数组2[根位置1:] #右子树的中序遍历结果num_left=len(left_arr2) #左子树的节点个数num_right=len(right_arr2) #右子树的节点个数left_arr1=arr1[0:num_left] #左子树的后序遍历结果right_arr1=arr1[num_left:-1] #右子树的后序遍历结果left _ root=after _ middle _ bintree(left _ arr 1，left_arr2) #递归重建左子树right _ root=after _ middle _ bin树(right _ arr 1，right_arr2) #递归重建右子树返回节点（根，左根，右根)#重建整棵树if _ _ name _ _= _ _ main _ _ :arr 1=[ D ， G ， E ， B ， F ， C ， A] #后序遍历结果arr2=[D ， B ， G ， E ， A ，c ， F] #中序遍历结果root=after_middle_bintree(arr1，arr2) #重建DFS _ after(root)print([x . val for x in result])#检测result=[]DFS _ middle(root)print([x . val for x in result])#检测运行结果为：
[D ， G ， E ， B ， F ， C ， A][D ， B ， G ， E ， A ， C ， F ]进程以退出代码0结束结语上面给出的是递归实现过程，比较容易实现，如果要写非递归形式，要用到栈，需要思考应该将什么入栈，应将根节点入栈。代码中用到了计算机编程语言的列表，需要注意切片arr[i:j]包含arr[i]但不包含a[j]，arr[i:-1]不包含最后一个元素，arr[:-1]是将到达)进行反转。
