Python二叉树的镜像

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

需要判断输入的结点为空或者输入的结点没有子树的情况。

  1. '''
  2. 操作给定的二叉树,将其变换为源二叉树的镜像。
  3. '''
  4. # -*- coding:utf-8 -*-
  5. class TreeNode:
  6. def __init__(self, x):
  7. self.val = x
  8. self.left = None
  9. self.right = None
  10. class Solution:
  11. # 递归实现
  12. def Mirror(self, root):
  13. if root == None:
  14. return
  15. if root.left == None and root.right == None:
  16. return root
  17. pTemp = root.left
  18. root.left = root.right
  19. root.right = pTemp
  20. self.Mirror(root.left)
  21. self.Mirror(root.right)
  22. # 非递归实现
  23. def Mirror2(self, root):
  24. if root == None:
  25. return
  26. stackNode = []
  27. stackNode.append(root)
  28. while len(stackNode) > 0:
  29. nodeNum = len(stackNode) - 1
  30. tree = stackNode[nodeNum]
  31. stackNode.pop()
  32. nodeNum -= 1
  33. if tree.left != None or tree.right != None:
  34. tree.left, tree.right = tree.right, tree.left
  35. if tree.left:
  36. stackNode.append(tree.left)
  37. nodeNum += 1
  38. if tree.right:
  39. stackNode.append(tree.right)
  40. nodeNum += 1
  41. # 非递归实现
  42. def MirrorNoRecursion(self, root):
  43. if root == None:
  44. return
  45. nodeQue = [root]
  46. while len(nodeQue) > 0:
  47. curLevel, count = len(nodeQue), 0
  48. while count < curLevel:
  49. count += 1
  50. pRoot = nodeQue.pop(0)
  51. pRoot.left, pRoot.right = pRoot.right, pRoot.left
  52. if pRoot.left:
  53. nodeQue.append(pRoot.left)
  54. if pRoot.right:
  55. nodeQue.append(pRoot.right)
  56. pNode1 = TreeNode(8)
  57. pNode2 = TreeNode(6)
  58. pNode3 = TreeNode(10)
  59. pNode4 = TreeNode(5)
  60. pNode5 = TreeNode(7)
  61. pNode6 = TreeNode(9)
  62. pNode7 = TreeNode(11)
  63. pNode1.left = pNode2
  64. pNode1.right = pNode3
  65. pNode2.left = pNode4
  66. pNode2.right = pNode5
  67. pNode3.left = pNode6
  68. pNode3.right = pNode7
  69. S = Solution()
  70. S.Mirror2(pNode1)
  71. print(pNode1.right.left.val)
解压密码: detechn或detechn.com

免责声明

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

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

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

Python树的子结构
« 上一篇 01-21
Python顺时针打印矩阵
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18476 篇
  • 评论总数:
    53229 条
  • 标签总数:
    8846 个
  • 总浏览量:
    21280636 次
  • 最后更新:
    1月22日

最多点赞

随便看看

标签TAG