題目：輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹(shù)中，左子樹(shù)的結(jié)點(diǎn)都大于右子樹(shù)的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹(shù)的鏡像轉(zhuǎn)換。 例如輸入：
???? 8

??? / \

? 6 ? 10

? /\??? /\

?5 7? 9 11
輸出：
???? 8

??? / \

? 10? 6

? /\? ? /\

11 9 7? 5

這題相對(duì)很簡(jiǎn)單，沒(méi)什么說(shuō)的，直接代碼了。。。

void BSTree::mirrorRec(BSTreeNode* node) {if (!node)return;mirrorRec(node->lc);mirrorRec(node->rc);BSTreeNode* temp = node->lc; //交換左、右子樹(shù)node->lc = node->rc;node->rc = temp; }void BSTree::mirrorRec() // 遞歸 {mirrorRec(root); }void BSTree::mirror() // 非遞歸 {stack<BSTreeNode*> st;st.push(root); //將二叉樹(shù)的根結(jié)點(diǎn)壓棧while (!st.empty()){BSTreeNode *t = st.top();BSTreeNode *temp;st.pop();temp = t->lc; //交換左、右子樹(shù)t->lc = t->rc;t->rc = temp;if (t->lc)st.push(t->lc);if (t->rc)st.push(t->rc);} }

?

?

總結(jié)

以上是生活随笔為你收集整理的程序员面试100题之十三：求二叉查找树的镜像的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。