## 本章堆棧樹圖相關的習題 **1、附近地點搜索** 找一個點集中與給定點距離最近的點，同時，給定的二維點集都是固定的，查詢可能有很多次，例如，坐標(39.91, 116.37)附近500米內有什么餐館，那么讓你來設計，該怎么做？  提示：可以建立R樹進行二維搜索，或使用GeoHash算法解決。 **2、最小操作數** 給定一個單詞集合Dict，其中每個單詞的長度都相同。現從此單詞集合Dict中抽取兩個單詞A、B，我們希望通過若干次操作把單詞A變成單詞B，每次操作可以改變單詞的一個字母，同時，新產生的單詞必須是在給定的單詞集合Dict中。求所有行得通步數最少的修改方法。 舉個例子如下： Given: A = "hit" B = "cog" Dict = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] 即把字符串A = "hit"轉變成字符串B = "cog"，有以下兩種可能： "hit" -> "hot" -> "dot" -> "dog" -> "cog"； "hit" -> "hot" -> "lot" -> "log" ->"cog"。 提示：建圖然后搜索。 **3、最少操作次數的簡易版** 給定兩個字符串，僅由小寫字母組成，它們包含了相同字符。 求把第一個字符串變成第二個字符串的最小操作次數，且每次操作只能對第一個字符串中的某個字符移動到此字符串中的開頭。 例如給定兩個字符串“abcd" "bcad" ，輸出：2，因為需要操作2次才能把"abcd"變成“bcad" ，方法是：abcd->cabd->bcad。 **3、把二元查找樹轉變成排序的雙向鏈表** 輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只調整指針的指向。例如把下述二叉查找樹 10 / / 6 14 / / / / 4 8 12 轉換成雙向鏈表，即得： 4=6=8=10=12=14=16。 **4、在二元樹中找出和為某一值的所有路徑** 輸入一個整數和一棵二元樹。 從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。 打印出和與輸入整數相等的所有路徑。 **5、判斷整數序列是不是二元查找樹的后序遍歷結果** 輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果，如果是返回true，否則返回false。 例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果： 8 / / 6 10 / / / / 5 7 9 11 因此返回true。 如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。 **6、設計包含min函數的棧** 定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素。要求函數min、push以及pop的時間復雜度都是O(1)。 **7、求二叉樹中節點的最大距離** 如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義"距離"為兩節點之間邊的個數。 請寫一個程序，求一棵二叉樹中相距最遠的兩個節點之間的距離。 **8** 輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。 例如輸入 8 / / 6 10 / / / / 5 7 9 11 輸出8 6 10 5 7 9 11。 **9** 請用遞歸和非遞歸倆種方法實現二叉樹的前序遍歷。 **10、求樹的深度** 輸入一棵二元樹的根結點，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。 例如：輸入二元樹： 10 / / 6 14 / / / 4 12 16 輸出該樹的深度3。 實現簡單的一個查找二叉樹的深度的函數。 **11、用倆個棧實現隊列** 某隊列的聲明如下： ```cpp template<typename T> class CQueue { public: CQueue() {} ~CQueue() {} void appendTail(const T& node); // append a element to tail void deleteHead(); // remove a element from head private: T> m_stack1; T> m_stack2; }; ``` 提示：這道題實質上是要求我們用兩個棧來實現一個隊列。棧是一種后入先出的數據容器，因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數據容器，我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。 **12** 假設有一顆二叉樹，已知這棵樹的節點上不均勻的分布了若干石頭，石頭數跟這棵二叉樹的節點數相同，石頭只可以在子節點和父節點之間進行搬運，每次只能搬運一顆石頭。請問如何以最少的步驟將石頭搬運均勻，使得每個節點上的石頭上剛好為1。 **13** 對于一顆完全二叉樹，要求給所有節點加上一個pNext指針，指向同一層的相鄰節點；如果當前節點已經是該層的最后一個節點，則將pNext指針指向NULL；給出程序實現，并分析時間復雜度和空間復雜度。 **14** 兩個用戶之間可能互相認識，也可能是單向的認識，用什么數據結構來表示？如果一個用戶不認識別人，而且別人也不認識他，那么他就是無效節點，如何找出這些無效節點？自定義數據接口并實現之，要求盡可能節約內存和空間復雜度。 **15** 有一個一億節點的樹，現在已知兩個點，找這兩個點的共同的祖先。 **16** 給一個二叉樹，每個節點都是正或負整數，如何找到一個子樹，它所有節點的和最大？ 提示：后序遍歷，每一個節點保存左右子樹的和加上自己的值。額外一個空間存放最大值。 寫完后序遍歷，面試官可能接著與你討論， - a). 如果要求找出只含正數的最大子樹，程序該如何修改來實現？ - b). 假設我們將子樹定義為它和它的部分后代，那該如何解決？ - c). 對于b，加上正數的限制，方案又該如何？ 總之，一道看似簡單的面試題，可能能變換成各種花樣。 比如，面試管可能還會再提兩個要求：第一，不能用全局變量；第二，有個參數控制是否要只含正數的子樹。 **17** 有一個排序二叉樹，數據類型是int型，如何找出中間大的元素。 **18** 中序遍歷二叉樹，結果為ABCDEFGH，后序遍歷結果為ABEDCHGF，那么前序遍歷結果為? **19** 寫程序輸出8皇后問題的所有排列，要求使用非遞歸的深度優先遍歷。 **20** 在8X8的棋盤上分布著n個騎士，他們想約在某一個格中聚會。騎士每天可以像國際象棋中的馬那樣移動一次，可以從中間像8個方向移動（當然不能走出棋盤），請計算n個騎士的最早聚會地點和要走多少天。要求盡早聚會，且n個人走的總步數最少，先到聚會地點的騎士可以不再移動等待其他的騎士。 從鍵盤輸入n（0<n<=64），然后一次輸入n個騎士的初始位置xi,yi（0<=xi,yi<=7）。屏幕輸出以空格分隔的三個數，分別為聚會點（x，y）以及走的天數。 提示：BFS。 **21、城市遍歷** 某人家住北京，想去青海玩，可能會經過許多城市，現已知地圖上的城市連接，求經過M個城市到達青海的路線種類。城市可以多次到達的，比如去了天津又回到北京，再去天津，即為3次。北京出發不算1次。 輸入： N M S N為城市總數，北京為0，青海為N-1； M為經過的城市數目； S為之后有S行 i j 表示第i個城市可以去第j個城市，是有方向的。 輸出： N 表示路徑種類。 **22** 給定兩個站點，如果沒有直達的路線，如何找到換乘次數最少的路線？ **23** 有兩座橋，其中一座可能是壞的，兩個守橋人分別守在這兩座橋的入口。他們一個總是會說實話，一個總是說謊話。 你現在需要找出哪一座橋可以通過。 請問最少需要問守橋人幾個問題，可以找出可以通過的橋？如何問？ **24** 一類似于蜂窩的結構的圖，進行搜索最短路徑（要求5分鐘）。 **25** 對于一顆完全二叉樹，要求給所有節點加上一個pNext指針，指向同一層的相鄰節點；如果當前節點已經是該層的最后一個節點，則將pNext指針指向NULL；給出程序實現，并分析時間復雜度和空間復雜度。