题解 | #二叉树的镜像#

# 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
        # """
        # method_1: 递归
        # 步骤： 
        # step1: 先深度最左端的节点，遇到空树返回，处理最左端的两个子节点交换位置
        # step2: 进入右子树， 继续按照先做后右再回中的方法访问
        # step3: 再返回到父问题，交换父问题的两个子节点的值
        # """
        # if not pRoot:
        #     return None
        # left = self.Mirror(pRoot.left)
        # right = self.Mirror(pRoot.right)

        # pRoot.left, pRoot.right = right, left
        # return pRoot

        def Mirror(self, pRoot: TreeNode) -> TreeNode:
            """
            method_2: 非递归
            步骤： 
            step1: 优先检查空树的情况
            step2: 使用栈辅助遍历二叉树，根节点先进栈
            step3: 遍历过程中每次弹出栈中一个元素，然后改节点左右节点分别入栈
            step4: 同时交换入栈的两个子节点的值， 因为子节点已经入栈，再交换，不担心后序没有交换。
            """
            if not pRoot:
                return None
            tmp_stack = list()
            tmp_stack.append(pRoot)

            while tmp_stack:
                node = tmp_stack[-1]
                tmp_stack.pop()
                if node.left:
                    tmp_stack.append(node.left)
                if node.right:
                    tmp_stack.append(node.right)
                tmp = node.left
                node.left = node.right
                node.right = tmp

            return pRoot
			好难过，又是一道