Question

题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。二叉树结点的定义如下：

树的镜像对很多人来说是一个新的概念，我们未必能够一下子想出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据照镜子的经验画出它的镜像。如图4.1中右边的二叉树就是左边的树的镜像。

图4.1　两棵互为镜像的二叉树

仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根结点相同，但它们的左右两个子结点交换了位置。因此我们不妨先在树中交换根结点的两个子结点，就得到图4.2中的第二棵树。

交换根结点的两个子结点之后，我们注意到值为10、6的结点的子结点仍然保持不变，因此我们还需要交换这两个结点的左右子结点。交换之后的结果分别是图4.2中的第三棵树和第四棵树。做完这两次交换之后，我们已经遍历完所有的非叶子结点。此时变换之后的树刚好就是原始树的镜像。

图4.2　求二叉树镜像的过程

注：（a）交换根结点的左右子树；（b）交换值为10的结点的左右子结点；（c）交换值为6的结点的左右子结点。

总结上面的过程，我们得出求一棵树的镜像的过程：我们先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后，就得到了树的镜像。

想清楚了这个思路，我们就可以动手写代码了。参考代码如下：

源代码

本题完整的源代码详见19_MirrorOfBinaryTree项目。

测试用例

- 功能测试（普通的二叉树，二叉树的所有结点都没有左子树或者右子树，只有一个结点的二叉树）。

- 特殊输入测试（二叉树的根结点为NULL指针）。

本题考点

- 考查对二叉树的理解。本题实质上是利用树的遍历算法解决问题。

- 考查应聘者的思维能力。树的镜像是一个抽象的概念，应聘者需要在短时间内想清楚求镜像的步骤并转化为代码。应聘者可以画图把抽象的问题形象化，这有助于其快速找到解题思路。

本题扩展

上面的代码是用递归实现的。如果要求用循环，该如何实现？