题目：

题解：
分析题意，我们可以看出输出结果是先序遍历，一开始是先访问的左边结点，然后是右边节点。而结果中是先访问的右边结点，然后是左边结点；即左边结点和右边结点进行了交换。因此，本题的核心是交换树的左右结点。

递归：
利用深度优先搜索，深度优先搜索包括二叉树的先序，中序，后序遍历；在本题中我们利用二叉树的先序遍历来进行求解，在输出当前结点的值之后，交换此结点的左右结点，然后再进行遍历。

代码如下：

class Solution:
    def mirrorTree(self, root):


    	def dfs(root):

    		if root is not None:

    			print(root.val)
    			# swap(root.left,root.right)
    			temp = root.left
    			root.left = root.right
    			root.right = temp


    			dfs(root.left)
    			dfs(root.right)

    	dfs(root)
    	return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

迭代：
参考：
广度优先搜索是二叉树的层次遍历，利用迭代的方法求解。

二叉树的层序遍历，需要借助队列来进行实现（利用队列实现先进先出，即在当前结点出队时，此结点的左右子结点开始依次进队，这样可以实现层次遍历的效果）。
本题只需要在左右结点入队之前，进行左右结点交换即可。

class Solution:
    def mirrorTree(self, root):

    	if not root:
    		return None



    	queue = [root]
    	while queue:

    		tmp = queue.pop(0)
    		tmp.left,temp.right = tmp.right,tmp.left

    		if tmp.left:
    			queue.append(tmp.left)
    		if tmp.right:
    			queue.append(tmp.right)


    	return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参考大佬的：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/solution/er-cha-shu-de-jing-xiang-di-gui-zhan-mo-ni-dui-lie/
堆栈实现：

class Solution:
    def mirrorTree(self, root):
        if not root:
            return None

        s = [root]

        while s:
            node = s.pop()#使后代得以遍历

            node.left, node.right = node.right, node.left
            
            if node.left:

                s.append(node.left)
            if node.right:

                s.append(node.right)

        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第二种方法和第三种方法一个是队列，一个是堆栈，在python中没有封装好的队列和堆栈，需要我们自己实现。从代码中可以看出，我们利用python的列表实现两种数据结构。队列先进先出，堆栈先进后出。
因此，在进行出去时，对于队列，是pop(0), 对于堆栈是pop()。