Python二叉搜索树的后续遍历序列

本文阅读 2 分钟
首页 Python笔记 正文
  1. '''
  2. 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。
  3. 如果是则输出Yes,否则输出No。
  4. 假设输入的数组的任意两个数字都互不相同。
  5. 二叉搜索树对于每一个非叶子节点, 均有结点左子节点<当前节点<结点右子节点
  6. '''
  7. # -*- coding:utf-8 -*-
  8. class Solution:
  9. def VerifySquenceOfBST(self, sequence):
  10. if sequence == []:
  11. return False
  12. root = sequence[-1]
  13. length = len(sequence)
  14. if min(sequence) > root or max(sequence) < root:
  15. return True
  16. index = 0
  17. # 二叉搜索树的左子树结点小于根节点
  18. '''
  19. 下面这个for循环特别需要主要index=i必须写在if语句外面,
  20. 否则就会发生当root结点前的所有元素小于root的时候, 正确判断应该为True,
  21. 但是因为if语句没有进入, index = 0 ,
  22. 在进入二叉搜索树的右子树结点大于根结点的for循环的时候, 因为sequence的数都小于root, 就会判断出错
  23. '''
  24. for i in range(length-1):
  25. index = i
  26. if sequence[i] > root:
  27. break
  28. # 二叉搜索树的右子树结点大于根结点
  29. # 这个循环中范围起始点必须是index+1, 不能为index
  30. # 因为当root结点前的所有元素小于root的时候,index=length-2,
  31. # 此时sequence[index]<root, 但是按照range(index, length-1), 第一个元素sequence[j]==sequence[index] < root, 返回False, 实际应该返回True才对
  32. # 而使用index+1, 因为已经默认index>root, 所以从后面一个开始盘算右子树结点是否大于root, 也不会影响结果
  33. for j in range(index+1, length-1):
  34. if sequence[j] < root:
  35. return False
  36. left = True
  37. if index > 0:
  38. left = self.VerifySquenceOfBST(sequence[:index])
  39. right = True
  40. if index < length-1:
  41. right = self.VerifySquenceOfBST(sequence[index:length-1])
  42. return left and right
  43. array = [5, 7, 6, 9, 11, 10, 8]
  44. array2 = [4, 6, 7, 5]
  45. array3 = [1, 2, 3, 4, 5]
  46. S = Solution()
  47. print(S.VerifySquenceOfBST(array))
  48. print(S.VerifySquenceOfBST(array2))
  49. print(S.VerifySquenceOfBST(array3))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python稀疏矩阵的转置
« 上一篇 01-21
Python八皇后问题
下一篇 » 01-21

发表评论