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

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

树的镜像是一个新的概念。如下图，右边的二叉树是左边二叉树的镜像。（很多面试题很抽象，不容易找到解决办法，可以画一些图形来帮助理解）

从图可以看出，要得出一棵树的镜像，可以前序遍历这棵树的每个结点，如果该结点有子结点，就交换它的两个子结点。当交换完所有非叶子结点之后，就得到了树的镜像。

参考代码如下：

void MirrorRecursively(BinaryTreeNode *pNode)
{
if ((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight == NULL))
return;

BinaryTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;

if (pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);

if (pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}

由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时，最简单的办法就是用一个辅助栈来模拟递归。首先把树的头结点放入栈中。在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中；如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。

实例代码如下：

void MirrorIteratively(BinaryTreeNode* pRoot)
{
if (pRoot == NULL)
return;

std::stack<BinaryTreeNode*> stackTreeNode;
stackTreeNode.push(pRoot);

while (stackTreeNode.size() > 0)
{
BinaryTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();

BinaryTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;

if (pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);

if (pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}