Python树的子结构

本文阅读 1 分钟
首页 Python笔记 正文

多出需要判断指针是不是None,避免访问空指针而造成程序崩溃。

  1. '''
  2. 输入两棵二叉树A,B,判断B是不是A的子结构
  3. 空树不是任意一个树的子结构
  4. '''
  5. class TreeNode:
  6. def __init__(self, x):
  7. self.val = x
  8. self.left = None
  9. self.right = None
  10. class Solution:
  11. def HasSubtree(self, pRoot1, pRoot2):
  12. result = False
  13. if pRoot1 != None and pRoot2 != None:
  14. if pRoot1.val == pRoot2.val:
  15. result = self.DoesTree1haveTree2(pRoot1, pRoot2)
  16. if not result:
  17. result = self.HasSubtree(pRoot1.left, pRoot2)
  18. if not result:
  19. result = self.HasSubtree(pRoot1.right, pRoot2)
  20. return result
  21. # 用于递归判断树的每个节点是否相同
  22. # 需要注意的地方是: 前两个if语句不可以颠倒顺序
  23. # 如果颠倒顺序, 会先判断pRoot1是否为None, 其实这个时候pRoot2的结点已经遍历完成确定相等了, 但是返回了False, 判断错误
  24. def DoesTree1haveTree2(self, pRoot1, pRoot2):
  25. if pRoot2 == None:
  26. return True
  27. if pRoot1 == None:
  28. return False
  29. if pRoot1.val != pRoot2.val:
  30. return False
  31. return self.DoesTree1haveTree2(pRoot1.left, pRoot2.left) and self.DoesTree1haveTree2(pRoot1.right, pRoot2.right)
  32. pRoot1 = TreeNode(8)
  33. pRoot2 = TreeNode(8)
  34. pRoot3 = TreeNode(7)
  35. pRoot4 = TreeNode(9)
  36. pRoot5 = TreeNode(2)
  37. pRoot6 = TreeNode(4)
  38. pRoot7 = TreeNode(7)
  39. pRoot1.left = pRoot2
  40. pRoot1.right = pRoot3
  41. pRoot2.left = pRoot4
  42. pRoot2.right = pRoot5
  43. pRoot5.left = pRoot6
  44. pRoot5.right = pRoot7
  45. pRoot8 = TreeNode(8)
  46. pRoot9 = TreeNode(9)
  47. pRoot10 = TreeNode(2)
  48. pRoot8.left = pRoot9
  49. pRoot8.right = pRoot10
  50. S = Solution()
  51. print(S.HasSubtree(pRoot1, pRoot8))
解压密码: detechn或detechn.com

免责声明

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

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

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

Python合并两个排序的链表
« 上一篇 01-21
Python二叉树的镜像
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18490 篇
  • 评论总数:
    53251 条
  • 标签总数:
    8863 个
  • 总浏览量:
    21642670 次
  • 最后更新:
    昨天 10:56

最多点赞

随便看看

标签TAG