【導讀】建任何新的結點，只調整指針的指向。很多與樹相關的題目都是用遞歸的思路來解決，本題也不。左子樹轉換成一個排好序的左子鏈表，再調整其右子樹轉換右子鏈表。最右結點、當前結點和右子鏈表的最左結點。按照這個方式遍歷樹，比較小的結點先訪問。

　　

【正文】 ，那么兩個數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了；同樣，當兩個數(shù)字的和大于輸入的數(shù)字 的時候，我們把較大的數(shù)字往前移動，因為排在數(shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。 我們把前面的思路整理一下：最初我們找到數(shù)組的第一個數(shù)字和最后一個數(shù)字。當兩個數(shù)字的和大于輸入的數(shù)字時，把較大的數(shù)字往前移動；當兩個數(shù)字的和小于數(shù)字時，把較小的數(shù)字往后移動；當相等時，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。 問題是這樣的思路是不是正確的呢？這需要嚴格的數(shù)學證明。感興趣的讀者可以自行證明一下。 參考代碼： /////////////////////////////////////////////////////////////////////// // 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。 } 擴展：如果輸入的數(shù)組是沒有排序的，但知道里面數(shù)字的范圍，其他條件不變，如和在 O(n)時間里找到這兩個數(shù)字？ (11)－求二元查找樹的鏡像 題目：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹 23 的結點都大于右子樹的結點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉換。 例如輸入： 8 / \ 6 10 /\ /\ 5 7 9 11 輸出： 8 / \ 10 6 /\ /\ 11 9 7 5 定義二元查找樹的結點為： 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 }。 分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺，就是交換結點的左右子樹。我們試著在遍歷例子中的二元查找樹的同時來交換每個結點的左右子樹。遍歷時首先訪問頭結點 8，我們交換它的左右子樹得到： 8 / \ 10 6 /\ /\ 9 11 5 7 我們發(fā)現(xiàn)兩個結點 6 和 10 的左右子樹仍然是左結點的值小于右結點的值，我們再試著交換他們的左右子樹，得到： 8 / \ 10 6 /\ /\ 11 9 7 5 剛好就是要求的輸出。 上面的分析印證了我們的直覺：在遍歷二元查找樹時每訪問到一個結點，交換它的左右子樹。這種思路用遞歸不難實現(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)。 } 由于遞歸的本質是編譯器生成了一個函數(shù)調用的棧，因此用循環(huán)來完成同樣任務時最簡單的辦法就是用一個輔助棧來模擬遞歸。首先我們把樹的頭結點放入棧中。在循環(huán)中，只要棧不為空，彈出棧的棧頂結點，交換它的左右子樹。如果它有左子樹，把它的左子樹壓入棧中；如果它有右子樹，把它的右子樹壓入棧中。這樣在下次循環(huá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)－從上往下遍歷二元樹 題目：輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。 例如輸入 8 / \ 6 10 /\ /\ 5 7 9 11 輸出 8 6 10 5 7 9 11。 分析：這曾是微軟的一道面試題。這道題實質上是要求遍歷一棵二元樹，只不過不是我們熟悉的前序、中序或者后序遍歷。 我們從樹的根結點開始分析。自然先應該打印根結點 8，同時為了下次能夠打印 8的兩個子結點，我們應該在遍歷到 8 時把子結點 6 和 10 保存到一個數(shù)據(jù)容器中?，F(xiàn)在數(shù)據(jù)容器中就有兩個元素 6 和 10 了。按照從左往右的要求，我們先取出 6 訪問。打印 6 的同時要把 6 的兩個子結點 5 和 7 放入數(shù)據(jù)容器中，此時數(shù)據(jù)容器中有三個元素 5 和 7。接下來我們應該從數(shù)據(jù)容器中取出結點 10 訪問了。注意 10 比 5 和 7 先放入容器，此時又比 5 和 7 先取出，就是我們通常說的先入先出。因此不難看出這個數(shù)據(jù)容器的類型應該是個隊列。 既然已經確定數(shù)據(jù)容器是一個隊列，現(xiàn)在的問題變成怎么實現(xiàn)隊列了。實際上我們無需自己動手實現(xiàn)一個，因為 STL已經為我們實現(xiàn)了一個很好的 deque（兩端都可以進出的隊列），我們只需要拿過來用就可以了。 我們知道樹是圖的一種特殊退化形式。同時如果對圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實際上是一種廣度優(yōu)先遍歷。因此這道題的本質是在二元樹上實現(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