题目标题

判断整数序列是不是二元查找树的后序遍历结果

参考解析
  1. # -*- coding:utf-8 -*-
  2. '''
  3. 方法功能:判断一个数组是否是二元查找数的后序遍历
  4. 输入参数:arr--数组
  5. 返回值:true--是,否则false
  6. '''
  7. def IsAfterOrder(arr,start,end):
  8. if arr == None:
  9. return False
  10. #数组的最后一个结点必定是根节点
  11. root = arr[end]
  12. #找到第一个大于root的值,那么前面所有结点都位于root左子树上
  13. i = start
  14. while i < end:
  15. if(arr[i]>root):
  16. break
  17. i += 1
  18. #如果序列是后续遍历序列,那么从i开始的所有值都应该大于根节点root的值
  19. j = i
  20. while j < end:
  21. if arr[j] < root:
  22. return False
  23. j += 1
  24. left_IsAfterOrder = True
  25. right_IsAfterOrder = True
  26. #判断小于root值的序列是否是某二元查找树的后续遍历
  27. if i > start:
  28. left_IsAfterOrder = IsAfterOrder(arr,start,i-1)
  29. #判断大于root值的序列是否是某二元查找树的后续遍历
  30. if j < end:
  31. right_IsAfterOrder = IsAfterOrder(arr,i,end)
  32. return left_IsAfterOrder and right_IsAfterOrder
  33. if __name__ == "__main__":
  34. arr = [1,3,2,5,7,6,4]
  35. result = IsAfterOrder(arr,0,len(arr)-1)
  36. i = 0
  37. while i < len(arr):
  38. print(arr[i])
  39. i += 1
  40. if result:
  41. print("是某一二元查找树的后续遍历序列")
  42. else:
  43. print("是某一二元查找树的后续遍历序列")