解题笔记—输入一颗二元查找树，将该树转换为它的镜像
问题描述：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入：
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<BSTreeNode *> 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的专栏”
补充：软件开发 , C语言 ,
