问题描述：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。

例如输入：

8

/ /

6 10

// //

5 7 9 11

输出：

8

/ /

10 6

// //

11 9 7 5

定义二元查找树的结点为：

view plaincopy to clipboardprint
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思路：题目要求用两种方法，递归和循环，其实质是一样的。

解法一：用递归。假设当前结点为pNode，只需交换该结点的左右子女，然后分别递归求解左子树和右子树即可。代码极为简单。

解法二：用循环，需要一个辅助栈完成，每次取栈顶元素交换左右子女，然后将左右子女分别压入辅助栈，当栈中元素为空时，结束循环。其实不论是递归也好，循环也好，都是利用栈的特性完成。

参考代码：

view plaincopy to clipboardprint
//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像
//函数参数 ： pRoot为根结点
//返回值 ： 根结点
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
BSTreeNode * pRight = pRoot->right;
BSTreeNode * pLeft = pRoot->left;
pRoot->left = Mirror_Solution1(pRight); //转化右子树
pRoot->right = Mirror_Solution1(pLeft); //转化左子树
}
return pRoot;
}
//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像
//函数参数 ： pRoot为根结点
//返回值 ： 根结点
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
BSTreeNode * pRight = pRoot->right;
BSTreeNode * pLeft = pRoot->left;
pRoot->left = Mirror_Solution1(pRight); //转化右子树
pRoot->right = Mirror_Solution1(pLeft); //转化左子树
}
return pRoot;
}

view plaincopy to clipboardprint
BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
stack stk; //辅助栈
stk.push(pRoot); //压入根结点
while(stk.size())
{
BSTreeNode *pNode = stk.top();
BSTreeNode *pLeft = pNode->left;
BSTreeNode* pRight = pNode->right;
stk.pop();

if(pLeft != NULL)
stk.push(pLeft);
if(pRight != NULL)
stk.push(pRight);
pNode->left = pRight; //交换左右子女
pNode->right = pLeft;
}
}
return pRoot;
}

本文出自“wuzhekai的专栏”