Python二叉树的镜像
需要判断输入的结点为空或者输入的结点没有子树的情况。
- '''
- 操作给定的二叉树,将其变换为源二叉树的镜像。
- '''
-
- # -*- coding:utf-8 -*-
- class TreeNode:
- def __init__(self, x):
- self.val = x
- self.left = None
- self.right = None
- class Solution:
- # 递归实现
- def Mirror(self, root):
- if root == None:
- return
- if root.left == None and root.right == None:
- return root
-
- pTemp = root.left
- root.left = root.right
- root.right = pTemp
-
- self.Mirror(root.left)
- self.Mirror(root.right)
-
- # 非递归实现
- def Mirror2(self, root):
- if root == None:
- return
- stackNode = []
- stackNode.append(root)
- while len(stackNode) > 0:
- nodeNum = len(stackNode) - 1
- tree = stackNode[nodeNum]
- stackNode.pop()
- nodeNum -= 1
- if tree.left != None or tree.right != None:
- tree.left, tree.right = tree.right, tree.left
- if tree.left:
- stackNode.append(tree.left)
- nodeNum += 1
- if tree.right:
- stackNode.append(tree.right)
- nodeNum += 1
- # 非递归实现
- def MirrorNoRecursion(self, root):
- if root == None:
- return
- nodeQue = [root]
- while len(nodeQue) > 0:
- curLevel, count = len(nodeQue), 0
- while count < curLevel:
- count += 1
- pRoot = nodeQue.pop(0)
- pRoot.left, pRoot.right = pRoot.right, pRoot.left
- if pRoot.left:
- nodeQue.append(pRoot.left)
- if pRoot.right:
- nodeQue.append(pRoot.right)
-
- pNode1 = TreeNode(8)
- pNode2 = TreeNode(6)
- pNode3 = TreeNode(10)
- pNode4 = TreeNode(5)
- pNode5 = TreeNode(7)
- pNode6 = TreeNode(9)
- pNode7 = TreeNode(11)
-
- pNode1.left = pNode2
- pNode1.right = pNode3
- pNode2.left = pNode4
- pNode2.right = pNode5
- pNode3.left = pNode6
- pNode3.right = pNode7
-
- S = Solution()
- S.Mirror2(pNode1)
- print(pNode1.right.left.val)
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。