問題描述：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換後的二元查找樹中，左子樹的結點都大於右子樹的結點。用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
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的專欄”
