不知道你有沒(méi)有這種困惑，雖然刷了很多算法題，當(dāng)我去面試的時(shí)候，面試官讓你手寫(xiě)一個(gè)算法，可能你對(duì)此算法很熟悉，知道實(shí)現(xiàn)思路，但是總是不知道該在什么地方寫(xiě)，而且很多邊界條件想不全面，一緊張，代碼寫(xiě)的亂七八糟。如果遇到?jīng)]有做過(guò)的算法題，思路也不知道從何尋找，那么這篇文章就主要為你解決這幾個(gè)問(wèn)題。

《劍指 offer》是準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)與算法面試的一本好書(shū)，里邊很多面試手寫(xiě)算法很多的注意的問(wèn)題，但是基本都是用 C++ 實(shí)現(xiàn)的，書(shū)中每章節(jié)的分類(lèi)都是按照性能和消耗以及手寫(xiě)代碼的注意的幾大點(diǎn)進(jìn)行了分類(lèi)，針對(duì)每個(gè)不同的點(diǎn)，進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法的混合實(shí)現(xiàn)。

二遍刷題，發(fā)現(xiàn)了還可以根據(jù)自身情況進(jìn)行整理和分類(lèi)。全部代碼是用 JS 書(shū)寫(xiě)，都經(jīng)過(guò) Leetcode 標(biāo)準(zhǔn)測(cè)試（小部分Leetcode 沒(méi)有的題目），對(duì)所有的算法題的特點(diǎn)進(jìn)行總結(jié)分類(lèi)，手寫(xiě)算法中，如何考慮到全部的邊界條件；如果快速多種思路解決，如何將思路快速的轉(zhuǎn)化為代碼，這是這一篇重點(diǎn)分享的地方。

二叉樹(shù)題目共有 11 題，我把這 11 題書(shū)中對(duì)實(shí)現(xiàn)方法和思路有詳細(xì)的講解，但是對(duì)于個(gè)人來(lái)說(shuō)，以后遇到陌生的二叉樹(shù)的題目怎么進(jìn)行解決，通過(guò)對(duì) 11 個(gè)題的分析、整理，得出以下幾個(gè)步驟，首先先來(lái)看這 11 個(gè)二叉樹(shù)經(jīng)典算法題。

PS：如果你已經(jīng)做過(guò)這幾道題，而且能夠順利的手寫(xiě)出來(lái)，不妨滑到最底部，希望最后的二叉樹(shù)思路、測(cè)試用例以及代碼編寫(xiě)的總結(jié)對(duì)你在面試中有所幫助（這篇文章精華所在）。

No.1

面試題7：重建二叉樹(shù)

已知前序遍歷為{1,2,4,7,3,5,6,8}，中序遍歷為{4,7,2,1,5,3,8,6}，它的二叉樹(shù)是怎么樣的？

1、

思路

根據(jù)前、中序遍歷的特點(diǎn)，（根左右、左根右），先根據(jù)前序遍歷確定根節(jié)點(diǎn)，然后在中序遍歷知道該根節(jié)點(diǎn)的左右樹(shù)的數(shù)量，反推出前序遍歷中左子樹(shù)的結(jié)點(diǎn)有哪些。根據(jù)該思路進(jìn)行遞歸即可完成二叉樹(shù)的重建。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)二叉樹(shù)，只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊二叉樹(shù)測(cè)試。

空樹(shù)、前序和中序不匹配 —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1//定義結(jié)點(diǎn) 2//classTreeNode{ 3//constructor(data){ 4//this.data=data; 5//this.left=null; 6//this.right=null; 7//} 8//} 9 10//參數(shù)：前序遍歷數(shù)組~中序遍歷數(shù)組 11constreConstructBinaryTree=(pre,vin)=>{ 12//判斷前序數(shù)組和中序數(shù)組是否為空 13if(!pre||pre.length===0||!vin||vin.length===0){ 14return; 15} 16//新建二叉樹(shù)的根節(jié)點(diǎn) 17vartreeNode={ 18val:pre[0] 19} 20//查找中序遍歷中的根節(jié)點(diǎn) 21for(vari=0;i

No.2

面試題8：二叉樹(shù)的下一節(jié)點(diǎn)

給定一個(gè)二叉樹(shù)的節(jié)點(diǎn)，如何找出中序遍歷的下一節(jié)點(diǎn)。有兩個(gè)指向左右子樹(shù)的指針，還有一個(gè)指向父節(jié)點(diǎn)的指針。

1、

思路

求中序遍歷的下一節(jié)點(diǎn)，就要分各種情況（明確中序遍歷下一結(jié)點(diǎn)在二叉樹(shù)中的位置有哪些），然后對(duì)某種情況詳細(xì)分析。

下一結(jié)點(diǎn)可能存在的情況：

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)二叉樹(shù)，只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊二叉樹(shù)測(cè)試。

空樹(shù)、前序和中序不匹配 —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1constgetNextNode=(pNode)=>{ 2//判斷該結(jié)點(diǎn)是否為null 3if(pNode==null){ 4return; 5} 6 7//當(dāng)前結(jié)點(diǎn)有右子樹(shù)且左子樹(shù) 8if(pNode.right!==null){ 9pNode=pNode.right; 10//判斷右子樹(shù)是否有左子樹(shù) 11while(pNode.left!==null){ 12pNode=pNode.left; 13} 14returnpNode; 15}else{ 16//判斷當(dāng)前結(jié)點(diǎn)是否存在父節(jié)點(diǎn)(如果為空,沒(méi)有下一結(jié)點(diǎn)) 17while(pNode.next!==null){ 18if(pNode==pNode.next.left){ 19returnpNode.next; 20}else{ 21pNode=pNode.next; 22} 23} 24//沒(méi)有下一結(jié)點(diǎn) 25returnnull; 26} 27}

No.3

面試題26：樹(shù)的子結(jié)構(gòu)

輸入兩棵二叉樹(shù) A 和 B，判斷 B 是不是 A 的子結(jié)構(gòu)。

1、

思路

通過(guò)判斷兩棵樹(shù)的根節(jié)點(diǎn)否相同，如果相同，則遞歸判斷樹(shù)剩余的結(jié)點(diǎn)是否相同。如果不相同，則遞歸樹(shù)的左右子節(jié)點(diǎn)進(jìn)行對(duì)比找到相同的根節(jié)點(diǎn)。

2、

測(cè)試用例

是子結(jié)構(gòu)、不是子結(jié)構(gòu) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)、只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn) —— 特殊測(cè)試。

空樹(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1constTreeConstrutor=(nodeA,nodeB)=>{ 2constresult=false; 3//判斷輸入是否為null 4//nodeA為null不會(huì)有子結(jié)構(gòu) 5if(nodeA==null){ 6returnfalse; 7} 8//如果nodeB為null,代表所有子結(jié)構(gòu)比較完成 9if(nodeB==null){ 10returntrue; 11} 12 13//如果根節(jié)點(diǎn)相同，則進(jìn)行子結(jié)構(gòu)全部的驗(yàn)證,返回驗(yàn)證的結(jié)果 14if(nodeA.data===nodeB.data){ 15result=match(nodeA,nodeB) 16} 17 18//如果根節(jié)點(diǎn)不相同，繼續(xù)遞歸遍歷查找相同的根節(jié)點(diǎn) 19returnTreeConstrutor(nodeA.left,nodeB)||TreeConstrutor(nodeA.right,nodeB) 20} 21 22//匹配根節(jié)點(diǎn)相同的子結(jié)構(gòu) 23constmatch=(nodeA,nodeB)=>{ 24if(nodeA==null){ 25returnfalse; 26} 27if(nodeB==null){ 28returntrue; 29} 30//判斷匹配的當(dāng)前結(jié)點(diǎn)是否相同 31if(nodeA.data==nodeB.data){ 32//遞歸匹配其他子節(jié)點(diǎn) 33returnmatch(nodeA.left,nodeB.left)&&match(nodeA.right,nodeB.right); 34} 35 36//如果不相同 37returnfalse; 38}

No.4

面試題27：二叉樹(shù)的鏡像

請(qǐng)完成一個(gè)函數(shù)，如果一個(gè)二叉樹(shù)，該函數(shù)輸出它的鏡像。

1、

思路

根節(jié)點(diǎn)的左右子節(jié)點(diǎn)相互交換，繼續(xù)遞歸遍歷，將子節(jié)點(diǎn)的左右結(jié)點(diǎn)進(jìn)行交換，知道遇到葉子節(jié)點(diǎn)。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)二叉樹(shù)，只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊二叉樹(shù)測(cè)試。

空樹(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1constinsert=(root)=>{ 2//判斷根節(jié)點(diǎn)是否為null 3if(root==null){ 4return; 5} 6 7//進(jìn)行結(jié)點(diǎn)交換 8LettempNode=root.left; 9root.left=root.right; 10root.right=tempNode; 11 12//遞歸遍歷剩余的子節(jié)點(diǎn) 13insert(root.left); 14insert(root.right); 15 16//返回根節(jié)點(diǎn) 17returnroot; 18}

No.5

面試題28：對(duì)稱(chēng)二叉樹(shù)

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一棵二叉樹(shù)是不是對(duì)稱(chēng)的。如果一棵二叉樹(shù)和它的鏡像一樣，那么它是對(duì)稱(chēng)的。

1、

思路

首先，觀察一個(gè)對(duì)稱(chēng)的二叉樹(shù)有什么特點(diǎn)？

結(jié)構(gòu)上：在結(jié)構(gòu)上實(shí)對(duì)稱(chēng)的，某一節(jié)點(diǎn)的左子節(jié)點(diǎn)和某一節(jié)點(diǎn)的右子節(jié)點(diǎn)對(duì)稱(chēng)。

規(guī)律上：我們?nèi)绻M(jìn)行前序遍歷（根、左、右），然后對(duì)前序遍歷進(jìn)行改進(jìn)（根、右、左），如果是對(duì)稱(chēng)的二叉樹(shù)，他們的遍歷結(jié)果是相同的。

考慮其他情況：

結(jié)點(diǎn)數(shù)量不對(duì)稱(chēng)

結(jié)點(diǎn)值不對(duì)稱(chēng)

2、

測(cè)試用例

對(duì)稱(chēng)二叉樹(shù)、不對(duì)稱(chēng)二叉樹(shù)（結(jié)點(diǎn)數(shù)量不對(duì)稱(chēng)、結(jié)點(diǎn)結(jié)構(gòu)不對(duì)稱(chēng)）—— 普通測(cè)試。

所有結(jié)點(diǎn)值都相同的二叉樹(shù) —— 特殊測(cè)試。

空二叉樹(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1varisSymmetric=(root)=>{ 2//判斷二叉樹(shù)是否為null——輸入測(cè)試，if(root==null){ 3returntrue; 4} 5 6//判斷輸入的二叉樹(shù),從根節(jié)點(diǎn)開(kāi)始判斷是否是對(duì)稱(chēng)二叉樹(shù) 7varSymmetric=(lNode,rNode)=>{ 8//判斷左右結(jié)點(diǎn)是否都為null 9if(lNode==null&&rNode==null){ 10returntrue; 11} 12//判斷其中一個(gè)為null另一個(gè)不是null 13if(lNode==null&&rNode!==null){ 14returnfalse; 15} 16if(lNode!==null&&rNode==null){ 17returnfalse; 18} 19//判斷兩個(gè)結(jié)點(diǎn)的值是否相同 20if(lNode.val!==rNode.val){ 21returnfalse; 22} 23//如果相同，繼續(xù)遞歸判斷其他的結(jié)點(diǎn) 24returnSymmetric(lNode.left,rNode.right)&&Symmetric(lNode.right,rNode.left) 25} 26 27Symmetric(root.left,root.right) 28}

No.6

面試題32：從上到下打印二叉樹(shù)

從上到下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印。（按層遍歷二叉樹(shù)）

1、

思路

從根節(jié)點(diǎn)開(kāi)始按層遍歷打印結(jié)點(diǎn)（自左往右），下一層的遍歷是上一層的字節(jié)點(diǎn)，但是我們發(fā)現(xiàn)想要獲取到上層結(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，上層的父節(jié)點(diǎn)已經(jīng)遍歷過(guò)去可，想要在獲取到，必須存儲(chǔ)父節(jié)點(diǎn)。然后下層遍歷的時(shí)候，自左往右取出父節(jié)點(diǎn)，依次打印子節(jié)點(diǎn)。

上方的解題思路中父節(jié)點(diǎn)的存儲(chǔ)和遍歷讓我們想到一個(gè)熟悉的數(shù)據(jù)結(jié)構(gòu)，對(duì)了，“先進(jìn)先出”的思想，那就是隊(duì)列。在遍歷上一層結(jié)點(diǎn)的時(shí)候，先打印結(jié)點(diǎn)值，然后判斷是夠存在左右子樹(shù)，如果存在，將給結(jié)點(diǎn)入隊(duì)，直到該層的結(jié)點(diǎn)全部遍歷完成。然后隊(duì)列出隊(duì)，分別打印結(jié)點(diǎn)，循環(huán)此步驟。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試

只有左、右子節(jié)點(diǎn)的二叉樹(shù)、只有一個(gè)節(jié)點(diǎn)的二叉樹(shù) —— 特殊測(cè)試

空樹(shù) —— 輸入測(cè)試

3、

代碼實(shí)現(xiàn)

1、參數(shù)：樹(shù)的根節(jié)點(diǎn)。

2、判斷是否為空。

3、打印結(jié)點(diǎn)值,判斷該結(jié)點(diǎn)是否存在子節(jié)點(diǎn)，如果存在就入隊(duì)。

4、出隊(duì)，打印結(jié)點(diǎn)

5、循環(huán)上述步驟

1varlevelOrder=function(root){ 2letresult=[];//存放遍歷的結(jié)果 3//判斷根節(jié)點(diǎn)是否為null 4if(root==null){ 5return[]; 6} 7//聲明一個(gè)隊(duì)列 8letqueue=[]; 9queue.push(root) 10 11//出隊(duì)，打印結(jié)結(jié)點(diǎn)、判斷是否存在子節(jié)點(diǎn) 12while(queue.length!==0){ 13lettemp=[];//存儲(chǔ)每層的結(jié)點(diǎn) 14letlen=queue.length; 15for(letj=0;j

No.7

面試題33：二叉樹(shù)的后序遍歷序列

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后續(xù)遍歷。如果是返回 true，如果不是返回 false。假設(shè)輸入的任意兩個(gè)數(shù)字互不相同。

1、

思路

根據(jù)后續(xù)遍歷的規(guī)律和二叉樹(shù)具備的特點(diǎn)，可以找到的規(guī)律就是（左、右、根）序列的最后一個(gè)數(shù)為根節(jié)點(diǎn)，又根據(jù)二叉樹(shù)的特點(diǎn)，左子節(jié)點(diǎn)小于根節(jié)點(diǎn)，右子節(jié)點(diǎn)大于根節(jié)點(diǎn)，分離出左右子節(jié)點(diǎn)，根據(jù)上邊的規(guī)律，遞歸剩下的序列。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)二叉樹(shù)，只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊二叉樹(shù)測(cè)試。

空樹(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1、參數(shù)：數(shù)組

2、判斷數(shù)組是否為空

3、取數(shù)組的最后一個(gè)元素作為對(duì)比的根節(jié)點(diǎn)

4、根據(jù)根節(jié)點(diǎn)值的大小分割數(shù)組（分割數(shù)組的同時(shí)判斷是否都滿足小于根節(jié)點(diǎn)的要求）

5、判斷分割數(shù)組是否是空

6、遞歸上方的步驟

1constisPostorder=(arr)=>{ 2//判斷數(shù)組是否為null 3if(arr.length==0){ 4returntrue; 5} 6 7//取數(shù)組最后一個(gè)數(shù)字為根節(jié)點(diǎn) 8letrootVal=arr[arr.length-1]; 9 10//搜索小于根節(jié)點(diǎn)的值,并記錄該結(jié)點(diǎn)的下標(biāo)(除根節(jié)點(diǎn)外) 11leti=0; 12for(;irootVal){ 14break 15} 16} 17 18//搜索大于根節(jié)點(diǎn)的值（除根節(jié)點(diǎn)外） 19letj=0; 20for(;jarr[j]){ 22returnfalse; 23} 24} 25 26//遞歸判斷左子節(jié)點(diǎn)的值（先判斷左子節(jié)點(diǎn)是夠有值），默認(rèn)返回true 27letleft=true 28if(i>0){ 29left=isPostorder(arr.slice(0,i)) 30} 31//如果右子樹(shù)不為空，判斷右子樹(shù)為二叉搜索樹(shù) 32letright=true 33if(i

No.8

面試34：二叉樹(shù)和為某一值路徑

輸入一棵二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中節(jié)點(diǎn)值的和為輸出整數(shù)的所有路徑。從樹(shù)的根節(jié)點(diǎn)開(kāi)始往下一直到葉子節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)形成一條路徑。

1、

思路

1、找規(guī)律：需要遍歷樹(shù)的所有結(jié)點(diǎn)：我們會(huì)想到前、中、后遍歷；需要存儲(chǔ)遍歷過(guò)的路徑（節(jié)點(diǎn)值）：我們想到用數(shù)組存儲(chǔ)

2、算法思想：前序遍歷（根、左、右）的特點(diǎn)，從根到葉子節(jié)點(diǎn)，會(huì)從樹(shù)自左向右依次遍歷二叉樹(shù)，所有可能的路徑都會(huì)遍歷到，所以使用前序遍歷更佳。

每遍歷一個(gè)結(jié)點(diǎn)就將其累加，然后判斷累加的值是否等于目標(biāo)值且子節(jié)點(diǎn)為葉子節(jié)點(diǎn)。如果是，則打印輸出該路徑；如果不是，則回退到上一父節(jié)點(diǎn)，此時(shí)數(shù)組中的數(shù)據(jù)結(jié)點(diǎn)進(jìn)行刪除，然后不斷的遍歷下一子節(jié)點(diǎn)，遞歸。

3、綜上所述，存儲(chǔ)結(jié)點(diǎn)路徑的時(shí)候，涉及到累加結(jié)點(diǎn)和刪除節(jié)點(diǎn)，我們可以將其抽象成入棧和出棧。然后遍歷二叉樹(shù)的所有路徑可以用到遞歸的過(guò)程，讓出棧和入棧與遞歸的狀態(tài)達(dá)成一致，這到題就不難了。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù)（有一條路徑滿足、有多條路徑滿足、都不滿足）—— 普通測(cè)試。

只有左子節(jié)點(diǎn)的二叉樹(shù)、只有右子節(jié)點(diǎn)的二叉樹(shù)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊測(cè)試。

空二叉樹(shù)、輸入負(fù)數(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1consttreeSum=(root,targetSum)=>{ 2//判斷輸入的二叉樹(shù)和整數(shù) 3if(root==null||targetSum{ 20//將當(dāng)前跟根節(jié)點(diǎn)進(jìn)行累加 21currentSum=currentSum+root.val; 22 23//存儲(chǔ)棧中 24pathStack.push(root.val); 25 26//判斷目標(biāo)值是否相等且是否為葉子節(jié)點(diǎn) 27if(currentSum==targetSum&&root.left==null&&root.right==null){ 28//打印路徑 29result.push(pathStack.slice(0)) 30} 31 32//如果左子節(jié)點(diǎn)不為空 33if(root.left!==null){ 34FindPath(root.left,targetSum,currentSum,pathStack,result); 35} 36 37//如果當(dāng)前結(jié)點(diǎn)還有右子樹(shù)，繼續(xù)遍歷 38if(root.right!==null){ 39FindPath(root.right,targetSum,currentSum,pathStack,result); 40} 41 42//該路徑遍歷到葉子節(jié)點(diǎn)，還沒(méi)有滿足條件，則退回到父節(jié)點(diǎn)，進(jìn)行下一結(jié)點(diǎn)的累加判斷 43pathStack.pop(); 44}

No.9

面試題37：序列化二叉樹(shù)

請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來(lái)序列化二叉樹(shù)和反序列化二叉樹(shù)。

1、

思路

1、序列化：遍歷二叉樹(shù)，遇到葉子節(jié)點(diǎn)，將其轉(zhuǎn)化為 $ 表示。

2、反序列化：根據(jù)前序遍歷的特點(diǎn)（根、左、右），進(jìn)行二叉樹(shù)的還原。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)二叉樹(shù)，只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊二叉樹(shù)測(cè)試。

空樹(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1letresult=[]; 2varserialize=function(root){ 3//判空 4if(root==null){ 5result.push('$'); 6return; 7} 8//前序遍歷 9result.push(root.val) 10serialize(root.left) 11serialize(root.right) 12//打印 13console.log(result) 14}; 15 16serialize(symmetricalTree);

No.10

面試題54：二叉樹(shù)的第 K 大節(jié)點(diǎn)

給定一棵二叉搜索樹(shù)，請(qǐng)找出其中的第 K 大節(jié)點(diǎn)。

1、

思路

要想找到第 K 大結(jié)點(diǎn)必要要知道排序，二叉樹(shù)的前、中、后遍歷中的中序遍歷就是從小到大排序。然后遍歷的同時(shí)計(jì)數(shù)找到第 K 大節(jié)點(diǎn)。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)的二叉樹(shù)、只有右子節(jié)點(diǎn)的二叉樹(shù)、只有一個(gè)節(jié)點(diǎn)的二叉樹(shù) —— 特殊測(cè)試。

K 的范圍、空樹(shù) —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1//求二叉樹(shù)中第K大節(jié)點(diǎn) 2varkthTallest=function(root,k){ 3letres=[] 4//遍歷 5constinorder=(root)=>{ 6if(root){ 7inorder(root.left); 8res.push(root.val); 9inorder(root.right); 10} 11} 12//調(diào)用 13inorder(root); 14returnres[res.length-k] 15};

No.11

面試題55：二叉樹(shù)的深度

輸入一棵二叉樹(shù)的根節(jié)點(diǎn)，求該樹(shù)的深度。從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)依次經(jīng)過(guò)的節(jié)點(diǎn)（包含根、葉子節(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度樹(shù)的深度。

1、

思路

思路一：按層遍歷，對(duì)按層遍歷的算法進(jìn)行改進(jìn)，每遍歷一次層進(jìn)行加一。

思路二：尋找最長(zhǎng)路徑，借助遍歷最長(zhǎng)路徑的設(shè)計(jì)思路記性改進(jìn)。只需記錄兩個(gè)子樹(shù)最深的結(jié)點(diǎn)為主。

2、

測(cè)試用例

完全二叉樹(shù)、非完全二叉樹(shù) —— 普通測(cè)試。

只有左子節(jié)點(diǎn)二叉樹(shù)，只有右子節(jié)點(diǎn)、只有一個(gè)結(jié)點(diǎn)的二叉樹(shù) —— 特殊二叉樹(shù)測(cè)試。

空樹(shù)、前序和中序不匹配 —— 輸入測(cè)試。

3、

代碼實(shí)現(xiàn)

1varmaxDepth=function(root){ 2//如果根節(jié)點(diǎn)為null 3if(root===null)return0; 4 5//遞歸左子樹(shù) 6letdepthLeft=maxDepth(root.left); 7 8//遞歸右子樹(shù) 9letdepthRight=maxDepth(root.right); 10 11//將子問(wèn)題合并求總問(wèn)題 12returnMath.max(depthLeft,depthRight)+1; 13};

總結(jié)歸納

通過(guò)《劍指 offer》以上十一個(gè)題，不是做過(guò)之后就記住了這么簡(jiǎn)單，而是通過(guò)以上二叉樹(shù)題型的總結(jié)歸納，能不能舉一反三，總結(jié)出二叉樹(shù)面試題的解題思路，以后遇到二叉樹(shù)相面試題能不能通過(guò)上邊總結(jié)出來(lái)的步驟進(jìn)行思考獨(dú)立解決，這是這篇文章的重點(diǎn)。下面就分別通過(guò)解題思路、測(cè)試用例以及編寫(xiě)代碼進(jìn)行深入總結(jié)。

解題思路總結(jié)

1、根據(jù)樹(shù)前（根左右）、中（左根右）、后（左右根）序遍歷的規(guī)律來(lái)解決問(wèn)題。

通過(guò)二叉樹(shù)的遍歷來(lái)找到規(guī)律，從而找到解題思路。

重建二叉樹(shù)

根據(jù)前、中序遍歷，找到二叉樹(shù)的根節(jié)點(diǎn)和左右子樹(shù)的規(guī)律，然后遞歸構(gòu)建二叉樹(shù)。

二叉樹(shù)的下一節(jié)點(diǎn)

根據(jù)中序遍歷，找出包含任何節(jié)點(diǎn)的一下節(jié)點(diǎn)的所有可能情況，然后根據(jù)情況分別進(jìn)行判斷。

二叉樹(shù)的后續(xù)遍歷序列

通過(guò)中序遍歷找到打印二叉樹(shù)結(jié)點(diǎn)的規(guī)律，可以判斷此后續(xù)遍歷是否為二叉樹(shù)。

二叉樹(shù)和為某一值的路徑

選擇二叉樹(shù)的遍歷，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行存儲(chǔ)判斷，然后根據(jù)二叉樹(shù)葉子節(jié)點(diǎn)的特點(diǎn)，進(jìn)行對(duì)問(wèn)題的解決。

二叉樹(shù)的第 K 大結(jié)點(diǎn)

中序遍歷的結(jié)果是從小到大，然后倒數(shù)找到第 K 大數(shù)據(jù)。

序列化二叉樹(shù)

遍歷二叉樹(shù)，遇到 null 轉(zhuǎn)化為特殊符號(hào)。

2、根據(jù)樹(shù)的結(jié)構(gòu)尋找規(guī)律來(lái)解決問(wèn)題

通過(guò)二叉樹(shù)的特點(diǎn)：左子節(jié)點(diǎn)小于父節(jié)點(diǎn)、右子節(jié)點(diǎn)大于父節(jié)點(diǎn)、樹(shù)的節(jié)點(diǎn)可以進(jìn)行遞歸等，以上特點(diǎn)又是更好的幫我們解決思路。

樹(shù)的子結(jié)構(gòu)

根據(jù)子結(jié)構(gòu)和主體樹(shù)的特點(diǎn)，對(duì)其樹(shù)的結(jié)構(gòu)進(jìn)行分析，可以找到解題的思路。

鏡像二叉樹(shù)

觀察鏡像二叉樹(shù)的左右子節(jié)點(diǎn)交換特點(diǎn)，可以找到解題思路。

對(duì)稱(chēng)二叉樹(shù)

觀察對(duì)稱(chēng)二叉樹(shù)有什么特點(diǎn)，在結(jié)構(gòu)上和遍歷上尋找特點(diǎn)和規(guī)律，可以找到解題思路。

按層遍歷二叉樹(shù)

根據(jù)二叉樹(shù)每層節(jié)點(diǎn)的結(jié)構(gòu)關(guān)系（父子關(guān)系），可以進(jìn)行每層遍歷，通過(guò)上層找到下層的遍歷結(jié)點(diǎn)。

反序列化二叉樹(shù)

根據(jù)遍歷的規(guī)律和二叉樹(shù)的規(guī)律，將遍歷結(jié)果生成一棵二叉樹(shù)。

測(cè)試用例總結(jié)

通過(guò)以上題目中，我將測(cè)試用例分為三大種，測(cè)試代碼的時(shí)候，在這三大種進(jìn)行想就可以了。

※普通測(cè)試

※特殊測(cè)試

※輸入測(cè)試

1

普通測(cè)試

普通測(cè)試從兩個(gè)方面去想，第一個(gè)方面就是問(wèn)題的本身，比如對(duì)稱(chēng)二叉樹(shù)的判斷，普通測(cè)試就是分別輸入一個(gè)對(duì)稱(chēng)二叉樹(shù)和非對(duì)稱(chēng)二叉樹(shù)進(jìn)行測(cè)試。第二個(gè)方面就是問(wèn)題本身沒(méi)有什么可以找到的測(cè)試，比如按層遍歷二叉樹(shù)，它的普通測(cè)試就是分別輸入完全二叉樹(shù)（普通二叉樹(shù)也可以），非完全二叉樹(shù)進(jìn)行測(cè)試。

2

特殊測(cè)試

特殊測(cè)試強(qiáng)調(diào)的是樹(shù)的特殊性，特殊的二叉樹(shù)就那么幾個(gè)，比如：只有左子節(jié)點(diǎn)的二叉樹(shù)、只有右子節(jié)點(diǎn)的二叉樹(shù)、只有一個(gè)節(jié)點(diǎn)的二叉樹(shù)、沒(méi)有結(jié)點(diǎn)的二叉樹(shù)。

3

輸入測(cè)試

輸入測(cè)試，顧名思義，要對(duì)用戶輸入的參數(shù)進(jìn)行判斷，比如，你輸入一棵樹(shù)，要判斷是否為空。再比如，求最大 K 結(jié)點(diǎn)，對(duì) K 的取值范圍進(jìn)行判斷。

代碼編寫(xiě)

將二叉樹(shù)的解題思路轉(zhuǎn)化為代碼除了熟練最基本的二叉樹(shù)的增、刪、改、查之外，最重要的就是二叉樹(shù)的遞歸，因?yàn)槎鏄?shù)的結(jié)構(gòu)決定了用遞歸解決二叉樹(shù)問(wèn)題更加簡(jiǎn)便。但是遞歸的書(shū)寫(xiě)并不僅簡(jiǎn)單，因?yàn)樗羞f和歸的過(guò)程，大腦并不能更好的去處理這些，可以去看之前總結(jié)遞歸的文章《數(shù)據(jù)結(jié)構(gòu)與算法之遞歸系列》。

書(shū)寫(xiě)二叉樹(shù)遞歸問(wèn)題有一點(diǎn)特別重要，不要嘗試的去想那個(gè)遞歸的過(guò)程，而是先去尋找到遞歸的終止條件，然后對(duì)每次遞歸的結(jié)果進(jìn)行判斷，然后讓他遞歸去吧，再次強(qiáng)調(diào)千萬(wàn)別去思考過(guò)程。

學(xué)習(xí)編程不是做了多少題，而是能不能在做過(guò)的題和項(xiàng)目中總結(jié)經(jīng)驗(yàn)，這是快速成長(zhǎng)的必要條件。非常感謝各位的大力支持，下一篇我們?cè)僖?jiàn)。