【正文】 直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。 // value of node BinaryTreeNode *m_pLeft。 當(dāng)訪問到某一結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)前結(jié)點(diǎn)的值。因此 我們?cè)诤瘮?shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。 currentSum // the sum of path ) { if(!pTreeNode) return。amp。 isLeaf) { std::vectorint::iterator iter =()。\t39。 // when we finish visiting a node and return to its parent node, // we should delete this node from the path and // minus the node39。 例如輸入 1， 2， 3， 4， 5， 6， 7 和 8 這 8 個(gè)數(shù)字，則最小的 4 個(gè)數(shù)字為 1， 2， 3 和 4。 我們可以開辟一個(gè)長度為 k 的數(shù)組。如果讀入的這個(gè)整數(shù)比數(shù)組中已有 k個(gè)整數(shù)的最大值要小，則用讀入的這個(gè)整數(shù)替換這 個(gè)最大值；如果讀入的整數(shù)比數(shù)組中已有 k 個(gè)整數(shù)的最大值還要大，則讀入的這個(gè)整數(shù)不可能是最小的 k 個(gè)整數(shù)之一，拋棄這個(gè)整數(shù)。不過從給面試官留下更好印象的角度出發(fā)，我們可以 11 進(jìn)一步把代碼寫得更漂亮一些。 另外，自己重頭開始寫一個(gè)最大堆需要一定量的代碼。 typedef multisetint, greaterint IntHeap。 if(k == 0 || () k) return。 ++ iter) { // if less than k numbers was inserted into leastNumbers if((()) k) (*iter)。 (*iter)。 如果輸入 5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回 false。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。 // the nodes in left subtree are less than the root int i = 0。 } // the nodes in the right subtree are greater than the root int j = i。 } // verify whether the left subtree is a BST bool left = true。 return (left amp。句子中單詞以空格符隔開。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和輸入時(shí)的順序保持一致。 while(pBegin pEnd) { char temp = *pBegin。 } } /////////////////////////////////////////////////////////////////////// // Reverse the word order in a sentence, but maintain the character // order inside a word // Input: pData the sentence to be reversed ///////////////////////////////////////////////////////////////////// 15 // char* ReverseSentence(char *pData) { if(pData == NULL) return NULL。\039。 // Reverse every word in the sentence pBegin = pEnd = pData。 39。 } // A word is between with pBegin and pEnd, reverse it else if(*pEnd == 39。) { Reverse(pBegin, pEnd)。 } 16 (08)－求 1+2+...+n 題目：求 1+2+…+n ，要求不能使用乘除法、 for、 while、 if、 else、 switch、 case 等關(guān)鍵 字以及條件判斷語句（ A?B:C）。由于已經(jīng)明確限制 for 和 while 的使用，循環(huán)已經(jīng)不能再用了。比如定義一個(gè)類，我們 new一含有 n 個(gè)這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會(huì)被調(diào)用 n次。 } static void Reset() { N = 0。 static int Sum。 int solution1_Sum(int n) { Temp::Reset()。 return Temp::GetSum()。從二選一我們很自然的想到布爾變量，比如 ture（ 1）的時(shí)候調(diào)用第一 17 個(gè)函數(shù)， false（ 0）的時(shí)候調(diào)用第二個(gè)函數(shù)。 A* Array[2]。 } }。a。 return value。 int solution3_f1(int i) { return 0。 }。當(dāng)編譯器看到 solution4_Sum100時(shí)，就是為模板類 solution4_Sum以參數(shù) 100生成該類型的代碼。這是該方法最大的缺點(diǎn)。鏈表結(jié)點(diǎn)定義 如下： struct ListNode { int m_nKey。可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。如果我們能夠得到鏈表中結(jié)點(diǎn)的個(gè)數(shù) n，那我們只要從頭結(jié) 點(diǎn)開始往后走 nk1 步就可以了。 如果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。 如果我們?cè)诒闅v時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開始遍歷，在第 k1步之前， 19 第二個(gè)指針保持不動(dòng)；在第 k1步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷。因此這一方法的時(shí)間效率前面的方法要高。 while(pCurm_pNext != NULL) { pCur = pCurm_pNext。 for(unsigned int i = 0。 } 思路二的參考代碼： ///////////////////////////////////////////////////////////////////// 20 // // Find the kth node from the tail of a list // Input: pListHead the head of list // k the distance to the tail // Output: the kth node from the tail of a list /////////////////////////////////////////////////////////////////////// ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k) { if(pListHead == NULL) return NULL。 i k。 // the distance between pAhead and pBehind is k // when pAhead arrives at the tail, p // Behind is at the kth node from the tail while(pAheadm_pNext != NULL) { pAhead = pAheadm_pNext。在軟件開發(fā)中，錯(cuò)誤的指針操作是大部分問題的 根源。含有循環(huán)的代碼經(jīng)常出的問題是在循環(huán)結(jié)束條件的判斷。如果各位感興趣，請(qǐng)自己分析并編寫代碼。 例如輸入數(shù)組 1 15 和數(shù)字 15。 我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個(gè)數(shù)。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng)；當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)字往后移動(dòng)；當(dāng)相等時(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。 int ahead = length 1。 num2 = data[ahead]。 // if the sum of two numbers is less than the input // increase the less number else behind ++。 例如輸入： 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。 分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺，就是交換結(jié)點(diǎn)的左右子樹。這種思路用遞歸不難實(shí)現(xiàn)，將遍歷二元查找樹的代碼稍作修改就可以了。 pNodem_pRight = pTemp。首先我們把樹的頭結(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。 ()。 // push left child subtree into stack if not null if(pNodem_pLeft) (pNodem_pLeft)。 分析：這曾是微軟的一道面試題?，F(xiàn)在數(shù)據(jù)容器中就有兩個(gè)元素 6 和 10 了。注意 10 比 5 和 7 先放入容器，此時(shí)又比 5 和 7 先取出，就是我們通常說的先入先出。 我們知道樹是圖的一種特殊退化形式。 struct BTreeNode // a node in the binary tree { int m_nValue。 /////////////////////////////////////////////////////////////////////// // Print a binary tree from top level to bottom level // Input: pTreeRoot the root of binary tree /////////////////////////////////////////////////////////////////////// void PrintFromTopToBottom(BTreeNode *pTreeRoot) { if(!pTreeRoot) return。 ()。 // print its right child s