1. 解题思路
仔细看题目描述里面的两颗二叉树，可以发现镜像二叉树的左右子树就是交换源二叉树的左右子树镜像后得到的！
所以只需先遍历求出源二叉树的left 和right 子树，然后再获取他们的镜像子树，最后交换镜像子树的位置即可得到。
2. 核心代码
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return TreeNode类
#
class Solution:
def Mirror(self , pRoot ):
# write code here
#当不存在二叉树的时候
if not pRoot:
return None
#先分别找到源二叉树的左子树和右子树
left = self.Mirror(pRoot.left)
right = self.Mirror(pRoot.right)
#然后开始翻转二叉树后，再让左子树 == 右子树,右子树 == 左子树即得到镜像二叉树
pRoot.left = right
pRoot.right = left
return pRoot3. 复杂度分析
- 时间复杂度：
(n为二叉树的所有节点，得到镜像树需要遍历所有节点)
- 空间复杂度：
---------------------------------------------我是解法二的分割线-----------------------------------------------------
4. 解法二
4.1 思路
熟悉二叉树的朋友应该都知道除了常用的递归解决法，还可以用辅助栈的方法来解决二叉树问题。那么这题用辅助栈的话，只需要遍历每一层的节点并放入栈中，然后交换每一层的左右子节点后放入镜像二叉树中；再剔除栈中节点，循环操作这几步直到栈为空，就可以得到镜像后的完整二叉树。具体图解如下：
- 创建空的辅助栈，放入根节点root：
- 弹出辅助栈中的根节点，放入镜像二叉树的根节点中：
- 接着来到左右子节点这里，先把6和10 加入辅助栈中，然后交换两者的位置放入镜像二叉树中，再依次弹出两者，后面循环这个步骤：
4.2 核心代码
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return TreeNode类
#
class Solution:
def Mirror(self , pRoot ):
# write code here
#当不存根节点时
if not pRoot:
return None
#创建辅助栈,把root加入辅助栈中
stack = []
stack.append(pRoot)
while stack:
#将源二叉树的节点按层加入辅助栈中，然后再依次迭代弹出
node = stack.pop()
#交换这个节点的左右子树
node.left, node.right = node.right, node.left
if node.left: #如果当前节点的左子树不为空，则放入辅助栈中
stack.append(node.left)
if node.right: #如果当前节点的右子树不为空，也放入辅助栈中
stack.append(node.right)
#返回最后的镜像二叉树
return pRoot4.3 复杂度分析
- 时间复杂度：
- 空间复杂度：
个节点，会占用 O(n)的额外空间)
京公网安备 11010502036488号