Python求树的宽度

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

求树的宽度
即树的某层所含结点数目最多, 则打印出该数字

  1. # -*- coding:utf-8 -*-
  2. class TreeNode:
  3. def __init__(self, x):
  4. self.val = x
  5. self.left = None
  6. self.right = None
  7. class Solution:
  8. def widthOfTree(self, pRoot):
  9. if pRoot == None:
  10. return 0
  11. nodeQue = [pRoot]
  12. levelCount, level, maxNum = {0: 1}, 0, 1
  13. while len(nodeQue):
  14. tempQue = nodeQue[:levelCount[level]]
  15. curNodeNum = 0
  16. while len(tempQue) > 0:
  17. tempQue.pop(0)
  18. pNode = nodeQue.pop(0)
  19. if pNode.left:
  20. nodeQue.append(pNode.left)
  21. curNodeNum += 1
  22. if pNode.right:
  23. nodeQue.append(pNode.right)
  24. curNodeNum += 1
  25. level += 1
  26. if level not in levelCount.keys():
  27. levelCount[level] = curNodeNum
  28. if curNodeNum > maxNum:
  29. maxNum = curNodeNum
  30. return maxNum
  31. pNode1 = TreeNode(1)
  32. pNode2 = TreeNode(2)
  33. pNode3 = TreeNode(3)
  34. pNode4 = TreeNode(4)
  35. pNode5 = TreeNode(5)
  36. pNode6 = TreeNode(6)
  37. pNode7 = TreeNode(7)
  38. pNode1.left = pNode2
  39. pNode1.right = pNode3
  40. pNode2.left = pNode4
  41. pNode2.right = pNode5
  42. pNode3.right = pNode6
  43. pNode3.left = pNode7
  44. S = Solution()
  45. width = S.widthOfTree(pNode1)
  46. print(width)
解压密码: detechn或detechn.com

免责声明

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

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

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

Python递归和非递归实现二叉搜索树的三种遍历
« 上一篇 01-21
Python实现逻辑斯蒂回归
下一篇 » 01-21

发表评论