【導(dǎo)讀】建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。很多與樹相關(guān)的題目都是用遞歸的思路來(lái)解決，本題也不。左子樹轉(zhuǎn)換成一個(gè)排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子鏈表。最右結(jié)點(diǎn)、當(dāng)前結(jié)點(diǎn)和右子鏈表的最左結(jié)點(diǎn)。按照這個(gè)方式遍歷樹，比較小的結(jié)點(diǎn)先訪問(wèn)。

　　

【正文】 ，那么兩個(gè)數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了；同樣，當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字 的時(shí)候，我們把較大的數(shù)字往前移動(dòng)，因?yàn)榕旁跀?shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。 我們把前面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng)；當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)字往后移動(dòng)；當(dāng)相等時(shí)，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。 問(wèn)題是這樣的思路是不是正確的呢？這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以自行證明一下。 參考代碼： /////////////////////////////////////////////////////////////////////// // Find two numbers with a sum in a sorted array // Output: ture is found such two numbers, otherwise false /////////////////////////////////////////////////////////////////////// bool FindTwoNumbersWithSum ( int data[], // a sorted array unsigned int length, // the length of the sorted array int sum, // the sum 22 intamp。 num1, // the first number, output intamp。 num2 // the second number, output ) { bool found = false。 if(length 1) return found。 int ahead = length 1。 int behind = 0。 while(ahead behind) { long long curSum = data[ahead] + data[behind]。 // if the sum of two numbers is equal to the input // we have found them if(curSum == sum) { num1 = data[behind]。 num2 = data[ahead]。 found = true。 break。 } // if the sum of two numbers is greater than the input // decrease the greater number else if(curSum sum) ahead 。 // if the sum of two numbers is less than the input // increase the less number else behind ++。 } return found。 } 擴(kuò)展：如果輸入的數(shù)組是沒(méi)有排序的，但知道里面數(shù)字的范圍，其他條件不變，如和在 O(n)時(shí)間里找到這兩個(gè)數(shù)字？ (11)－求二元查找樹的鏡像 題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹 23 的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。 例如輸入： 8 / \ 6 10 /\ /\ 5 7 9 11 輸出： 8 / \ 10 6 /\ /\ 11 9 7 5 定義二元查找樹的結(jié)點(diǎn)為： struct BSTreeNode // a node in the binary search tree (BST) { int m_nValue。 // value of node BSTreeNode *m_pLeft。 // left child of node BSTreeNode *m_pRight。 // right child of node }。 分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺(jué)，就是交換結(jié)點(diǎn)的左右子樹。我們?cè)囍诒闅v例子中的二元查找樹的同時(shí)來(lái)交換每個(gè)結(jié)點(diǎn)的左右子樹。遍歷時(shí)首先訪問(wèn)頭結(jié)點(diǎn) 8，我們交換它的左右子樹得到： 8 / \ 10 6 /\ /\ 9 11 5 7 我們發(fā)現(xiàn)兩個(gè)結(jié)點(diǎn) 6 和 10 的左右子樹仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，我們?cè)僭囍粨Q他們的左右子樹，得到： 8 / \ 10 6 /\ /\ 11 9 7 5 剛好就是要求的輸出。 上面的分析印證了我們的直覺(jué)：在遍歷二元查找樹時(shí)每訪問(wèn)到一個(gè)結(jié)點(diǎn)，交換它的左右子樹。這種思路用遞歸不難實(shí)現(xiàn)，將遍歷二元查找樹的代碼稍作修改就可以了。參考代碼如下： /////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) recursively // the head of BST in initial call ///////////////////////////////////////////////////////////////////// 24 // void MirrorRecursively(BSTreeNode *pNode) { if(!pNode) return。 // swap the right and left child subtree BSTreeNode *pTemp = pNodem_pLeft。 pNodem_pLeft = pNodem_pRight。 pNodem_pRight = pTemp。 // mirror left child subtree if not null if(pNodem_pLeft) MirrorRecursively(pNodem_pLeft)。 // mirror right child subtree if not null if(pNodem_pRight) MirrorRecursively(pNodem_pRight)。 } 由于遞歸的本質(zhì)是編譯器生成了一個(gè)函數(shù)調(diào)用的棧，因此用循環(huán)來(lái)完成同樣任務(wù)時(shí)最簡(jiǎn)單的辦法就是用一個(gè)輔助棧來(lái)模擬遞歸。首先我們把樹的頭結(jié)點(diǎn)放入棧中。在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點(diǎn)，交換它的左右子樹。如果它有左子樹，把它的左子樹壓入棧中；如果它有右子樹，把它的右子樹壓入棧中。這樣在下次循環(huán)中就能交換它兒子結(jié)點(diǎn)的左右子樹了。參考代碼如下： /////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) Iteratively // Input: pTreeHead: the head of BST /////////////////////////////////////////////////////////////////////// void MirrorIteratively(BSTreeNode *pTreeHead) { if(!pTreeHead) return。 std::stackBSTreeNode*stackTreeNode。 (pTreeHead)。 while(()) { BSTreeNode *pNode = ()。 ()。 25 // swap the right and left child subtree BSTreeNode *pTemp = pNodem_pLeft。 pNodem_pLeft = pNodem_pRight。 pNodem_pRight = pTemp。 // push left child subtree into stack if not null if(pNodem_pLeft) (pNodem_pLeft)。 // push right child subtree into stack if not null if(pNodem_pRight) (pNodem_pRight)。 } } (12)－從上往下遍歷二元樹 題目：輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。 例如輸入 8 / \ 6 10 /\ /\ 5 7 9 11 輸出 8 6 10 5 7 9 11。 分析：這曾是微軟的一道面試題。這道題實(shí)質(zhì)上是要求遍歷一棵二元樹，只不過(guò)不是我們熟悉的前序、中序或者后序遍歷。 我們從樹的根結(jié)點(diǎn)開始分析。自然先應(yīng)該打印根結(jié)點(diǎn) 8，同時(shí)為了下次能夠打印 8的兩個(gè)子結(jié)點(diǎn)，我們應(yīng)該在遍歷到 8 時(shí)把子結(jié)點(diǎn) 6 和 10 保存到一個(gè)數(shù)據(jù)容器中。現(xiàn)在數(shù)據(jù)容器中就有兩個(gè)元素 6 和 10 了。按照從左往右的要求，我們先取出 6 訪問(wèn)。打印 6 的同時(shí)要把 6 的兩個(gè)子結(jié)點(diǎn) 5 和 7 放入數(shù)據(jù)容器中，此時(shí)數(shù)據(jù)容器中有三個(gè)元素 5 和 7。接下來(lái)我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點(diǎn) 10 訪問(wèn)了。注意 10 比 5 和 7 先放入容器，此時(shí)又比 5 和 7 先取出，就是我們通常說(shuō)的先入先出。因此不難看出這個(gè)數(shù)據(jù)容器的類型應(yīng)該是個(gè)隊(duì)列。 既然已經(jīng)確定數(shù)據(jù)容器是一個(gè)隊(duì)列，現(xiàn)在的問(wèn)題變成怎么實(shí)現(xiàn)隊(duì)列了。實(shí)際上我們無(wú)需自己動(dòng)手實(shí)現(xiàn)一個(gè)，因?yàn)?STL已經(jīng)為我們實(shí)現(xiàn)了一個(gè)很好的 deque（兩端都可以進(jìn)出的隊(duì)列），我們只需要拿過(guò)來(lái)用就可以了。 我們知道樹是圖的一種特殊退化形式。同時(shí)如果對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。因此這道題的本質(zhì)是在二元樹上實(shí)現(xiàn)廣度優(yōu)先遍歷。 參考代碼： include deque 26 include iostream using namespace std。 struct BTreeNode // a node in the binary tree { int m_nValue。 // value of node BTreeNode *m_pLeft。 // left child of node BTreeNode *m_pRight。 // right child of node }。 /////////////////////////////////////////////////////////////////////// // Print a binary tree from top level to bottom level // Input: pTreeRoot the root of binary tree /////////////////////////////////////////////////////////////////////// void PrintFromTopToBottom(BTreeNode *pTreeRoot) { if(!pTreeRoot) return。 // get a empty queue dequeBTreeNode * dequeTreeNode。 // insert the root at the tail of queue (pTreeRoot)。 while(()) { // get a node from the head of queue BTreeNode *pNode = ()。 ()。 // print the node cout pNodem_nValue 39。 39。 // print its left child subtree if it has if(pNodem_pLeft) (pNodem_pLeft)。 // print its right child subt