【正文】 正是這個(gè)用途。由于題目與字符出現(xiàn)的次數(shù)相關(guān)，我們是不是可以統(tǒng)計(jì)每個(gè)字符在該字符串中出現(xiàn)的次數(shù)？要達(dá)到這個(gè)目的，我們需要一個(gè)數(shù)據(jù)容器來存放每個(gè)字符的出現(xiàn)次數(shù)。如果字符串有n個(gè)字符，每個(gè)字符可能與后面的O(n)個(gè)字符相比較，因此這種思路時(shí)間復(fù)雜度是O(n2)?？吹竭@道題時(shí)，最直觀的想法是從頭開始掃描這個(gè)字符串中的每個(gè)字符。如輸入abaccdeff，則輸出b。字號(hào)：大中小 }}程序員面試題精選100題(13)－第一個(gè)只出現(xiàn)一次的字符字符串 20070321 21:17:22 閱讀5465 評(píng)論30 // print its left child subtree if it has if(pNodem_pLeft) (pNodem_pLeft)。 // print the node cout pNodem_nValue 39。 while(()) { // get a node from the head of queue BTreeNode *pNode = ()。 // get a empty queue dequeBTreeNode * dequeTreeNode。 // right child of node}。 // value of node BTreeNode *m_pLeft。參考代碼：include dequeinclude iostreamusing namespace std。同時(shí)如果對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。實(shí)際上我們無需自己動(dòng)手實(shí)現(xiàn)一個(gè)，因?yàn)镾TL已經(jīng)為我們實(shí)現(xiàn)了一個(gè)很好的deque（兩端都可以進(jìn)出的隊(duì)列），我們只需要拿過來用就可以了。因此不難看出這個(gè)數(shù)據(jù)容器的類型應(yīng)該是個(gè)隊(duì)列。接下來我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點(diǎn)10訪問了。按照從左往右的要求，我們先取出6訪問。現(xiàn)在數(shù)據(jù)容器中就有兩個(gè)元素6我們從樹的根結(jié)點(diǎn)開始分析。分析：這曾是微軟的一道面試題。 例如輸入 8 / \ 6 10訂閱 // push right child subtree into stack if not null if(pNodem_pRight) (pNodem_pRight)。 pNodem_pRight = pTemp。 // swap the right and left child subtree BSTreeNode *pTemp = pNodem_pLeft。while(()) { BSTreeNode *pNode = ()。 std::stackBSTreeNode*stackTreeNode。這樣在下次循環(huán)中就能交換它兒子結(jié)點(diǎn)的左右子樹了。在循環(huán)中，只要棧不為空，彈出棧的棧頂結(jié)點(diǎn)，交換它的左右子樹。 }由于遞歸的本質(zhì)是編譯器生成了一個(gè)函數(shù)調(diào)用的棧，因此用循環(huán)來完成同樣任務(wù)時(shí)最簡單的辦法就是用一個(gè)輔助棧來模擬遞歸。 // mirror left child subtree if not null if(pNodem_pLeft) MirrorRecursively(pNodem_pLeft)。 pNodem_pLeft = pNodem_pRight。參考代碼如下：///////////////////////////////////////////////////////////////////////// Mirror a BST (swap the left right child of each node) recursively// the head of BST in initial call///////////////////////////////////////////////////////////////////////void MirrorRecursively(BSTreeNode *pNode){ if(!pNode) return。上面的分析印證了我們的直覺：在遍歷二元查找樹時(shí)每訪問到一個(gè)結(jié)點(diǎn)，交換它的左右子樹。 /\11 9/\ /\9 11 5 7我們發(fā)現(xiàn)兩個(gè)結(jié)點(diǎn)6和10的左右子樹仍然是左結(jié)點(diǎn)的值小于右結(jié)點(diǎn)的值，我們?cè)僭囍粨Q他們的左右子樹，得到： 8 / \ 10 6我們?cè)囍诒闅v例子中的二元查找樹的同時(shí)來交換每個(gè)結(jié)點(diǎn)的左右子樹。 // right child of node}。 // value of node BSTreeNode *m_pLeft。 /\11 9/\ /\5 7 9 11輸出： 8 / \ 10 6用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。字號(hào)：大中小}擴(kuò)展：如果輸入的數(shù)組是沒有排序的，但知道里面數(shù)字的范圍，其他條件不變，如何在O(n)時(shí)間里找到這兩個(gè)數(shù)字程序員面試題精選100題(11)－求二元查找樹的鏡像樹 20070315 09:36:33 閱讀3906 評(píng)論9 // if the sum of two numbers is