【正文】 // Convert the left subtree if (pCurrentm_pLeft != NULL) 4 ConvertNode(pCurrentm_pLeft, pLastNodeInList)。 pLastNodeInList) { if(pNode == NULL) return。 } /////////////////////////////////////////////////////////////////////// // 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)。 } // 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。 } BSTreeNode *pTemp = pNode。 // Connect the least node in the right subtree to the current node if(pRight) { pNodem_pRight = pRight。 pNodem_pLeft = pLeft。 // Convert the left subtree if(pNodem_pLeft) pLeft = ConvertNode(pNodem_pLeft, false)。 BSTreeNode *pLeft = NULL。 // right child of node }。 // value of node BSTreeNode *m_pLeft。當(dāng)所有結(jié)點(diǎn)都訪問過之后，整棵樹也就轉(zhuǎn)換成一個(gè)排序雙向鏈表了。按照這個(gè)方式遍歷樹，比較小的結(jié)點(diǎn)先訪問。從樹的根結(jié)點(diǎn)開始遞歸調(diào)整所有結(jié)點(diǎn)。 思路一：當(dāng)我們到達(dá)某一結(jié)點(diǎn)準(zhǔn)備調(diào)整以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹時(shí)，先調(diào)整其左子樹將左子樹轉(zhuǎn)換成一個(gè)排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子 鏈表。很多與樹相關(guān)的題目都是用遞歸的思路來解決，本題也不例外。 比如將二元查找樹 10 / \ 6 14 / \ / \ 4 8 12 16 轉(zhuǎn)換成雙向鏈表 4=6=8=10=12=14=16。 1 (01)把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。 分析：本題是微軟的面試題。下面我們用兩種不同的遞歸思路來分析。最近鏈接左子鏈表的最右結(jié)點(diǎn)（左子樹的最大結(jié)點(diǎn)）、當(dāng)前結(jié)點(diǎn)和右子鏈表的最左結(jié)點(diǎn)（右子樹的最小結(jié)點(diǎn)）。 思路二：我們可以中序遍歷整棵樹。如果我們每訪問一個(gè)結(jié)點(diǎn)，假設(shè)之前訪問過的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。 參考代碼： 首先我們定義二元查找樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下： struct BSTreeNode // a node in the binary search tree { int m_nValue。 // left child of node BSTreeNode *m_pRight。 思路一對(duì)應(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 *pRight = NULL。 // Connect the greatest node in the left subtree to the current node if(pLeft) { pLeftm_pRight = pNode。 } // Convert the right subtree if(pNodem_pRight) pRight = ConvertNode(pNodem_pRight, true)。 pRightm_pLeft = 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。 } return pTemp。 } 思路二對(duì)應(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。 BSTreeNode *pCurrent = pNode。 // Put the current node into the doublelinked list pCurrentm_pLeft = pLastNodeInList。 pLastNodeInList = pCurrent。 } /////////////////////////////////////////////////////////////////////// // 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。 // Get the head of the doublelinked list BSTreeNode *pHeadOfList = pLastNodeInList。amp。 return pHeadOfList。要求函數(shù) min、push 以及 pop 的時(shí)間復(fù)雜度都是 O(1)。 我看到這道題目時(shí)，第一反應(yīng)就是每次 push 一個(gè)新元素時(shí)，將棧里所有逆序元素排序。但由于不能保證最后 push 進(jìn)棧的元素最先出棧，這種思路設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個(gè)棧了。每次 push 一個(gè)新元素進(jìn)棧的時(shí)候，如果該元素比當(dāng)前的最小元素 還要小，則更新最小元素。但仔細(xì)一想，該思路存在一個(gè)重要的問題：如果當(dāng)前最小元素被pop 出去，如何才能得到下一個(gè)最小元素？ 因此僅僅只添加一個(gè)成員變量存放最小元素（或最小元素的位置）是不夠的。每次 push 一個(gè)新元素的時(shí)候，同時(shí)將最小元素（或最小元素的位置。 參考代碼： include deque include template typename T class CStackWithMin { public: CStackWithMin(void) {} virtual ~CStackWithMin(void) {} Tamp。 const Tamp。 void push(const Tamp。 void pop(void)。 min(void) const。// theelements of stack size_tm_minIndex。 // get the last element of mutable stack template typename T Tamp。 } // get the last element of nonmutable stack template typename T const Tamp。 6 } // insert an elment at the end of stack template typename T void CStackWithMinT::push(const Tamp。 // set the index of minimum elment in m_data at the end of m_minIndex if(() == 0) (0)。 else (())。 // pop m_minIndex ()。 CStackWithMinT::min() const { assert(() 0)。 return m_data[()]。但如果能注意一些細(xì)節(jié)無疑能在面試中加分。如果別人的元素類型只是 int 類型，模板將能給面試官帶來好印象； ? 兩個(gè)版本的 top 函數(shù)。把代碼寫的盡量安全是每個(gè)軟件公司對(duì)程序員的要求； ? 添加一些注釋。說不定代碼中的幾個(gè)小亮點(diǎn)就能讓自己輕松拿到心儀的 Offer。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。要求時(shí)間復(fù)雜度為 O(n)。 分析：本題最初為 2020 年浙江大學(xué)計(jì)算機(jī)系的考研題的最后一道程序設(shè)計(jì)題，在 2020 年里包括 google 在內(nèi)的很多知名公司都把本題當(dāng)作面試題。 如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。因此這種思路的時(shí)間是 O(n3)。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來的累加