[牛客网刷题 Day6] JZ27 二叉树的镜像

题目：

操作给定的二叉树，将其变换为源二叉树的镜像。

思路

返回的是一棵树，那得建立TreeNode吧，想到了两种方法：
① 使用队列，从右往左存node，这样读出来的顺序就是镜像的；可是答案要求输出一颗树，我不知道怎么转换成树
② 使用递归，当孩子为叶节点时，交换左右节点的位置；可是还是写不来，o(╥﹏╥)o

偷偷看了答案，用堆栈存储节点，每次取出来就交换左右节点，于是照着这个思路写了一下代码：

# 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: TreeNode) -> TreeNode:
        # write code here
        if pRoot is None:
            return None 
        q = []
        q.append(pRoot)
        
        while len(q):
            for i in range(len(q)):
                node = q.pop()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                # swap
                tmp = node.left
                node.left = node.right
                node.right = tmp
        return pRoot        
        

答案：

看了看递归：
解题步骤：
1、特判：如果pRoot为空，返回空
2、交换左右子树
3、把pRoot的左子树放到Mirror中镜像一下
4、把pRoot的右子树放到Mirror中镜像一下
5、返回根节点root

class Solution:
    def Mirror(self , pRoot ):
        # write code here
        if not pRoot:
            return pRoot
        # 左右子树交换
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        # 递归左右子树
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        
        return pRoot

网上搜了一下递归的解法：

解决递归问题一般就三步曲，分别是：

第一步，定义函数功能 -> 翻转树
第二步，寻找递归终止条件 -> 已经是叶节点了or已经为空了
第二步，递推函数的等价关系式 -> 翻转node的左子树和右子树