【正文】 1 (01)把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。 比如將二元查找樹 10 / \ 6 14 / \ / \ 4 8 12 16 轉(zhuǎn)換成雙向鏈表 4=6=8=10=12=14=16。 分析：本題是微軟的面試題。很多與樹相關(guān)的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。 思路一：當我們到達某一結(jié)點準備調(diào)整以該結(jié)點為根結(jié)點的子樹時，先調(diào)整其左子樹將左子樹轉(zhuǎn)換成一個排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子 鏈表。最近鏈接左子鏈表的最右結(jié)點（左子樹的最大結(jié)點）、當前結(jié)點和右子鏈表的最左結(jié)點（右子樹的最小結(jié)點）。從樹的根結(jié)點開始遞歸調(diào)整所有結(jié)點。 思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結(jié)點先訪問。如果我們每訪問一個結(jié)點，假設(shè)之前訪問過的結(jié)點已經(jīng)調(diào)整成一個排序雙向鏈表，我們再把調(diào)整當前結(jié)點的指針將其鏈接到鏈表的末尾。當所有結(jié)點都訪問過之后，整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表了。 參考代碼： 首先我們定義二元查找樹結(jié)點的數(shù)據(jù)結(jié)構(gòu)如下： struct BSTreeNode // a node in the binary search tree { int m_nValue。 // value of node BSTreeNode *m_pLeft。 // left child of node BSTreeNode *m_pRight。 // right child of node }。 思路一對應(yīng)的代碼： /////////////////////////////////////////////////////////////////////// // Covert a sub binarysearchtree into a sorted doublelinked list 2 // Input: pNode the head of the sub tree // asRight whether pNode is the right child of its parent // Output: if asRight is true, return the least node in the subtree // else return the greatest node in the subtree /////////////////////////////////////////////////////////////////////// BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight) { if(!pNode) return NULL。 BSTreeNode *pLeft = NULL。 BSTreeNode *pRight = NULL。 // Convert the left subtree if(pNodem_pLeft) pLeft = ConvertNode(pNodem_pLeft, false)。 // Connect the greatest node in the left subtree to the current node if(pLeft) { pLeftm_pRight = pNode。 pNodem_pLeft = pLeft。 } // Convert the right subtree if(pNodem_pRight) pRight = ConvertNode(pNodem_pRight, true)。 // Connect the least node in the right subtree to the current node if(pRight) { pNodem_pRight = pRight。 pRightm_pLeft = pNode。 } BSTreeNode *pTemp = pNode。 // If the current node is the right child of its parent, // return the least node in the tree whose root is the current node if(asRight) { while(pTempm_pLeft) 3 pTemp = pTempm_pLeft。 } // If the current node is the left child of its parent, // return the greatest node in the tree whose root is the current node else { while(pTempm_pRight) pTemp = pTempm_pRight。 } return pTemp。 } /////////////////////////////////////////////////////////////////////// // Covert a binary search tree into a sorted doublelinked list // Input: the head of tree // Output: the head of sorted doublelinked list /////////////////////////////////////////////////////////////////////// BSTreeNode* Convert(BSTreeNode* pHeadOfTree) { // As we want to return the head of the sorted doublelinked list, // we set the second parameter to be true return ConvertNode(pHeadOfTree, true)。 } 思路二對應(yīng)的代碼： /////////////////////////////////////////////////////////////////////// // Covert a sub binarysearchtree into a sorted doublelinked list // Input: pNode the head of the sub tree // pLastNodeInList the tail of the doublelinked list /////////////////////////////////////////////////////////////////////// void ConvertNode(BSTreeNode* pNode, BSTreeNode*amp。 pLastNodeInList) { if(pNode == NULL) return。 BSTreeNode *pCurrent = pNode。 // Convert the left subtree if (pCurrentm_pLeft != NULL) 4 ConvertNode(pCurrentm_pLeft, pLastNodeInList)。 // Put the current node into the doublelinked list pCurrentm_pLeft = pLastNodeInList。 if(pLastNodeInList != NULL) pLastNodeInListm_pRight = pCurrent。 pLastNodeInList = pCurrent。 // Convert the right subtree if (pCurrentm_pRight != NULL) ConvertNode(pCurrentm_pRight, pLastNodeInList)。 } /////////////////////////////////////////////////////////////////////// // Covert a binary search tree into a sorted doublelinked list // Input: pHeadOfTree the head of tree // Output: the head of sorted doublelinked list /////////////////////////////////////////////////////////////////////// BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree) { BSTreeNode *pLastNodeInList = NULL。 ConvertNode(pHeadOfTree, pLastNodeInList)。 // Get the head of the doublelinked list BSTreeNode *pHeadOfList = pLastNodeInList。 while(pHeadOfList amp。amp。 pHeadOfListm_pLeft) pHeadOfList = pHeadOfListm_pLeft。 return pHeadOfList。 } (02)設(shè)計包含 min函數(shù) 的棧 題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個 min 函數(shù)，能夠得到棧的最小元素。要求函數(shù) min、push 以及 pop 的時間復(fù)雜度都是 O(1)。 分析：這是去年 google 的一道面試題。 我看到這道題目時，第一反應(yīng)就是每次 push 一個新元素時，將棧里所有逆序元素排序。這 5 樣棧頂元素將是最小元素。但由于不能保證最后 push 進棧的元素最先出棧，這種思路設(shè)計的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個棧了。 在棧里添加一個成員變量存放最小元素（或最小元素的位置）。每次 push 一個新元素進棧的時候，如果該元素比當前的最小元素 還要小，則更新最小元素。 乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果當前最小元素被pop 出去，如何才能得到下一個最小元素？ 因此僅僅只添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次 push 一個新元素的時候，同時將最小元素（或最小元素的位置?？紤]到棧元素的類型可能是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，用最小元素的位置將能減少空間消耗） push到輔助棧中；每次 pop 一個元素出棧的時候，同時 pop 輔助棧。 參考代碼： include deque include template typename T class CStackWithMin { public: CStackWithMin(void) {} virtual ~CStackWithMin(void) {} Tamp。 top(void)。 const Tamp。 top(void) const。 void push(const Tamp。 value)。 void pop(void)。 const Tamp。 min(void) const。 private: Tm_data。// theelements of stack size_tm_minIndex。// the indicesof minimum elements }。 // get the last element of mutable stack template typename T Tamp。 CStackWithMinT::top() { return ()。 } // get the last element of nonmutable stack