问答题 6.  输入一个整数数组,判断该数组是否是某二元查找树的后序遍历的结果。如果是,那么返回true,否则返回false。例如数组[1,3,2,5,7,6,4]就是下图中二叉树的后序遍历序列。
   
【正确答案】二元查找树的特点是:对于任意一个结点,它的左子树上所有结点的值都小于这个结点的值,它的右子树上所有结点的值都大于这个结点的值。根据它的这个特点以及二元查找树后序遍历的特点,可以看出,这个序列的最后一个元素一定是树的根结点(上图中的结点4),然后在数组中找到第一个大于根结点4的值5,那么结点5之前的序列(1,3,2)对应的结点一定位于结点4的左子树上,结点5(包含这个结点)后面的序列一定位于结点4的右子树上(也就是说结点5后面的所有值都应该大于或等于4)。对于结点4的左子树遍历的序列{1,3,2}以及右子树的遍历序列{5,7,6}可以采用同样的方法来分析,因此,可以通过递归方法来实现,实现代码如下:
   """
   方法功能: 判断一个数组是否是二元查找树的后续遍历序列
   输入参数: arr:数组:
   返回值: true:是, 否则返回false
   """
   def IsAfterOrder(arr,start,end):
   if arr==None:
   return False
   #数组的最后一个结点必定是根结点
   root=arr[end]
   #找到第一个大于root的值, 那么前面所有的结点都位于root的左子树上
   i=start
   while i<end:
   if(arr[i]>root):
   break
   i+=1
   #如果序列是后续遍历的序列, 那么从i开始的所有值都应该大于根结点root的值
   j=i
   while j<end:
   if arr[j]<root:
   return False
   j+=1
   left_IsAfterOrder=True
   right_IsAfterOrder=True
   #判断小于root值的序列是否是某一二元查找树的后续遍历
   if i>start:
   left_IsAfierOrder=IsAfterOrder(arr,start,i-1)
   #判断大于root值的序列是否是某一二元查找树的后续遍历
   if j<end:
   right_IsAfterOrder=IsAfterOrder(arr,i,end)
   return left_IsAfterOrder and right_IsAfterOrder
   
   if __name__="__main__":
   arr=[1,3,2,5,7,6,4]
   result=IsAfterOrder(arr,0,len(arr)-1)
   i=0
   while i<len(arr):
   print arr[i],
   i+-=1
   if result:
   print "是某一二元查找树的后续遍历序列"
   else:
   print "不是某一二元查找树的后续遍历序列"
   程序的运行结果为:
   1 3 2 5 7 6 4是某一二元查找树的后序遍历序列
   算法性能分析:
   这种方法对数组只进行了一次遍历,因此,时间复杂度O(N)。
【答案解析】[考点] 如何判断一个数组是否是二元查找树后序遍历的序列