1、法律o本課件包括：演示文稿，示例，代碼，題庫，和聲音等，小象學(xué)院擁有完全知識產(chǎn)權(quán)的權(quán)利；只限于善意學(xué)習(xí)者在本課程使用，不得在課程范圍外向任何第散播。任何其他人或機構(gòu)不得盜版、仿造其中的者的權(quán)利。創(chuàng)意，保留一切通過法律o課程n咨詢：小象：ChinaHadoopn新浪互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者第五課二叉樹與圖林沐互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者內(nèi)容概述1.5道經(jīng)典二叉樹與圖的相關(guān)題目預(yù)備知識:二叉樹基礎(chǔ)知識例1:路徑之和2(medium)(二叉樹深搜)例2:最近的公共祖先(medium)(二叉樹性質(zhì))例3:二叉樹轉(zhuǎn)鏈表(medium) (二叉樹與鏈表)預(yù)備知識:二叉樹層次遍歷例4:側(cè)面觀察二叉樹(medium)

2、 (二叉樹寬搜)預(yù)備知識:圖的基礎(chǔ)知識例5:課程安排(有向圖環(huán))(medium)2.詳細講解題目解題方法、代碼實現(xiàn)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹定義樹是n(n>=0)個節(jié)點的有限集，且這些節(jié)點滿足如下關(guān)系:(1) 有且僅有一個節(jié)點沒有父結(jié)點，該節(jié)點稱為樹的根。(2) 除根外，其余的每個節(jié)點都有且僅有一個父結(jié)點。一個以它為根的樹。(3)樹中的每一個節(jié)點都二叉樹在滿足樹的條件時，滿足如下條件:(子樹)，這兩個子樹有左右之分，次序不可顛倒。每個節(jié)點最多有互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹構(gòu)造預(yù)備知識:二叉樹的深度遍歷互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹的遍歷課堂練習(xí)預(yù)備知識:二叉

3、樹的遍歷講解例1:路徑之和2給定一個二叉樹與整數(shù)sum，找出所有從根節(jié)點到葉結(jié)點的路徑，這些路徑上的節(jié)點值累加和為sum。選自 LeetCode 113. Path Sum II難度:Medium互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:思考深度搜索所有從根節(jié)點到葉結(jié)點的路徑，檢查各路徑上所有節(jié)點的值的和是否為sum。思考:1.使用何種數(shù)據(jù)結(jié)構(gòu)遍歷路徑上的節(jié)點？2.在樹的前序遍歷時做什么?后序遍歷時做什么?一個節(jié)點為葉結(jié)點?當(dāng)遍歷到葉結(jié)點時應(yīng)該做什么?3.如何互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:算法思路至path棧中(vector實1.從根節(jié)點深度遍歷二叉樹，先序遍歷時，將該節(jié)點值現(xiàn))，使用 path_value累

4、加節(jié)點值。2.當(dāng)遍歷至葉結(jié)點時，檢查path_value值是否為sum，若為sum，則將path push進入result結(jié)果中。3.在后續(xù)遍歷時，將該節(jié)點值從path棧出，path_value減去節(jié)點值。例1:算法思路互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:算法思路互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:算法思路互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:算法思路互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:課堂練習(xí)3分鐘填寫代碼，有問題隨時提出！例1:實現(xiàn)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例1:測試與leetcode提交結(jié)果例2:最近的公共祖先已知二叉樹，求二叉樹中給定的兩個節(jié)點的最近公共祖先。最近公共祖先: 兩節(jié)點v與w的最近公共祖先u，滿足在樹上最低(離

5、根最遠)，且v,w兩個節(jié)點都是u的子孫。選自 LeetCode 236. Lowest Common Ancestor of a Binary Tree難度:Medium互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:思考與分析1. 兩個節(jié)點的公共祖先一定在從根節(jié)點，至這兩個節(jié)點的路徑上。2. 由于求公共祖先中的最近公共祖先，那么即同時出現(xiàn)在這兩條路徑上的離根節(jié)點最遠的節(jié)點(或離兩個最近)。徑上最后一個相同3.最終算法即:求p節(jié)點路徑，q節(jié)點路徑，的節(jié)點。互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:求根節(jié)點至某節(jié)點路徑(深度搜索)1.從根節(jié)點遍歷(搜索)至該節(jié)點，找到該節(jié)點后就結(jié)束搜索。2.將遍歷過程中遇到的節(jié)點按照順序起來，這

6、些節(jié)點即路徑節(jié)點。例2:求根節(jié)點至某節(jié)點路徑(棧路徑)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:求根節(jié)點至某節(jié)點路徑(實現(xiàn)，課堂練習(xí))3分鐘時間填寫代碼，有問題隨時提出！互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:求根節(jié)點至某節(jié)點路徑(實現(xiàn))互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:求徑上最后一個相同的節(jié)點1. 求出較短路徑的長度n。2. 同時遍歷p節(jié)點的路徑與q節(jié)點的路徑，遍歷n個節(jié)點，最后一個發(fā)現(xiàn)的相同節(jié)點，即最近公共祖先。互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:整體代碼(實現(xiàn)，課堂練習(xí))3分鐘時間填寫代碼，有問題隨時提出！例2:整體代碼(實現(xiàn))互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例2:測試與leetcode提交結(jié)果互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:二叉樹轉(zhuǎn)鏈表給

7、定一個二叉樹，將該二叉樹就地(in-place)轉(zhuǎn)換為單鏈表。單鏈表中節(jié)點順序為二叉樹前序遍歷順序。選自 LeetCode 114. Flatten Binary Tree to Linked List難度:Medium互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:思考前序遍歷二叉樹，將節(jié)點指針push進入vector，順序遍歷vector中的節(jié)點，相鄰兩節(jié)點，形成鏈單鏈表。(投機取巧)該方法雖然可通過題目，但不滿足就地(in-place)轉(zhuǎn)換的條件。若就地(in-place)轉(zhuǎn)換應(yīng)該如何做？互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:方法1課堂練習(xí)3分鐘填寫代碼，有問題隨時提出！互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:方法1實現(xiàn)互聯(lián)網(wǎng)新

8、技術(shù)教育領(lǐng)航者例3:算法思路(方法2整體)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:算法思路(拆解并解決子問題)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:算法思路(解決當(dāng)前問題)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例3:方法2課堂練習(xí)5分鐘填寫代碼，有問題隨時提出！例3:方法2實現(xiàn)例3:測試與leetcode提交結(jié)果課間休息10分鐘有問題提出！互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹層次遍歷二叉樹層次遍歷，又稱為寬度優(yōu)先搜索，按樹的層次依次樹的結(jié)點。層次遍歷使用隊列對遍歷節(jié)點進行遍歷拓展其左孩子與右孩子。，先進入隊列的結(jié)點，優(yōu)先互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹層次遍歷互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹層次遍歷，課堂練習(xí)互聯(lián)網(wǎng)新

9、技術(shù)教育領(lǐng)航者預(yù)備知識:二叉樹層次遍歷，實現(xiàn)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例4:側(cè)面觀察二叉樹給定一個二叉樹，假設(shè)從該二叉樹的右側(cè)觀察它，將觀察到的節(jié)點按照從上到下的順序輸出。選自 LeetCode 199. Binary Tree Right Side View難度:Medium互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例4:思考與分析從二叉樹的右側(cè)觀察它，將觀察到的節(jié)點按照從上到下的順序輸出，就是求層次遍歷二叉樹，每個層中的最后一個節(jié)點。思考:層次遍歷時，如何每一層中出現(xiàn)的最后一個節(jié)點?互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例4:算法思路層次遍歷時，將節(jié)點與層數(shù)綁定為pair，壓入隊列時，將節(jié)點與層數(shù)同時壓入隊列，并每一層中出現(xiàn)的最

10、后一個節(jié)點。在層次遍歷中，每一層中的最后一個節(jié)點最后遍歷到，隨時更新對每層的最后一個節(jié)點即可。互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例4:課堂練習(xí)5分鐘填寫代碼，有問題隨時提出！例4:實現(xiàn)例4:測試與leetcode提交結(jié)果互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:圖的定義圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V, E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。圖分無向圖與有向圖，根據(jù)圖的邊長，又分帶權(quán)圖與不帶權(quán)圖。互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:圖的構(gòu)造與表示(臨接矩陣)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:圖的構(gòu)造與表示(臨接表)預(yù)備知識:圖的深度優(yōu)先遍歷從圖

11、中某個頂點v出發(fā)，首先該頂點，然后依次從它的各個未被的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通且未被的頂點都被到。 若此時尚有其他頂點未被的頂點作起始點，重復(fù)上述過程，直至圖中所有到，則另選一個未被頂點都被到為止。互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:圖的深度優(yōu)先遍歷，課堂練習(xí)3分鐘填寫代碼，有問題隨時提出！預(yù)備知識:圖的深度優(yōu)先遍歷，實現(xiàn)預(yù)備知識:圖的寬度優(yōu)先遍歷從圖中某個頂點v出發(fā)，在分別從這些鄰接點出發(fā)依次了v之后依次v的各個未曾過的鄰接點，然后的頂點的鄰接點先它們的鄰接點，并使得“先被于后被”，直至圖中所有已被的頂點的鄰接點都被訪的頂點的鄰接點被問到。如果此時圖中尚有頂點未被

12、，則需要另選一個未曾被過的頂點作為新的起始點，重復(fù)上述過程，直至圖中所有頂點都被到為止。互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:圖的寬度優(yōu)先遍歷，課堂練習(xí)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者預(yù)備知識:圖的寬度優(yōu)先遍歷，實現(xiàn)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:課程安排已知有n個課程，標記從0至n-1，課程之間是有依賴關(guān)系的， 例如希望完成A課程，可能需要先完成B課程。已知n個課程的依賴關(guān)系，求是否可以將n個課程全部完成。選自 LeetCode 207. Course Schedule難度:Medium互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:分析n個課程，它們之間有m個依賴關(guān)系，可以看成頂點個數(shù)為n，邊個數(shù)為m的有向圖。圖1:n = 3,

13、 m = 0, 1, 0, 2, 1, 2；可以完成。圖2:n = 3, m = 0, 1, 1, 2, 2, 0；不可以完成。故，若有向圖無環(huán)，則可以完成全部課程，否則不能。問題轉(zhuǎn)圖是否有環(huán)。換成，構(gòu)建圖，并互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:方法1，深度優(yōu)先搜索在深度優(yōu)先搜索時，如果正在搜索某一頂點(還未遞歸深度搜索)，又回到了該頂點，即證明圖有環(huán)。如下圖:該頂點的互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:算法思路(無環(huán))互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:算法思路(無環(huán))互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:算法思路(有環(huán))互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:方法1，調(diào)用代碼互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:方法1，課堂練習(xí)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:方法1，實現(xiàn)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者例5:方法2，拓撲排序(寬度優(yōu)先搜索)在寬度優(yōu)先搜索時，只將入度為0的點添加至隊列。當(dāng)完成一個頂點的搜索(從隊列取出)，它指向的所有頂點入度都減1，若此時某頂點入度為0則添加至隊列，若完成寬