今天是小浩算法 “365刷題計劃” 二叉樹入門 - 整合篇。本篇作為入門整合篇，已經砍去難度較大的知識點，所有列出的内容，均為必須掌握。因為很長，寫下目錄：
二叉樹是啥
二叉樹的最大深度（dfs）
二叉樹的層次周遊（bfs）
二叉搜尋樹驗證
二叉搜尋樹查找
二叉搜尋樹删除
平衡二叉樹
完全二叉樹
二叉樹的剪枝
二叉樹有多重要？單就面試而言，在 leetcode 中二叉樹相關的題目占據了300多道，近三分之一。同時，二叉樹在整個算法闆塊中還起到承上啟下的作用：不但是數組和連結清單的延伸，又可以作為圖的基礎。總之，非常重要！
什麼是二叉樹？官方是這樣定義的：在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。
上面那是個玩笑，二叉樹長這樣：
二叉樹常被用于實作二叉查找樹和二叉堆。樹比連結清單稍微複雜，因為連結清單是線性資料結構，而樹不是。樹的問題很多都可以由廣度優先搜尋或深度優先搜尋解決。
一般而言，我們會看到下面這些與樹相關的術語：
小浩概念
與樹相關的術語
樹的結點（node）：包含一個資料元素及若幹指向子樹的分支；
孩子結點（child node）：結點的子樹的根稱為該結點的孩子；
雙親結點：b 結點是a 結點的孩子，則a結點是b 結點的雙親；
兄弟結點：同一雙親的孩子結點；堂兄結點：同一層上結點；
祖先結點: 從根到該結點的所經分支上的所有結點
子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫
結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；
樹的深度：樹中最大的結點層
結點的度：結點子樹的個數
樹的度：樹中最大的結點度。
葉子結點：也叫終端結點，是度為 0 的結點；
分枝結點：度不為0的結點；
有序樹：子樹有序的樹，比如家族樹；
無序樹：不考慮子樹的順序；
了解了上面的基本概念之後。我們将通過幾道例題，為大家引入樹的經典操作。
複習上面的概念：樹的深度指的是樹中最大的結點層。
第104題：給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例：
給定二叉樹 [3,9,20,null,null,15,7]，
基本概念掌握：每個節點的深度與它左右子樹的深度有關，且等于其左右子樹最大深度值加上 1。即：
maxdepth(root) =
max(maxdepth(root.left),maxdepth(root.right)) + 1
以 [3,9,20,null,null,15,7] 為例：
我們要對根節點的最大深度求解，就要對其左右子樹的深度進行求解
我們看出。以4為根節點的子樹沒有左右節點，其深度為1。而以20為根節點的子樹的深度，同樣取決于它的左右子樹深度。
對于15和7的子樹，我們可以一眼看出其深度為1。
由此我們可以得到根節點的最大深度為
根據分析，我們通過遞歸進行求解：
其實我們上面用的遞歸方式，本質上是使用了dfs的思想。是以這裡就可以引出什麼是dfs：深度優先搜尋算法（depth first search），對于二叉樹而言，它沿着樹的深度周遊樹的節點，盡可能深的搜尋樹的分支，這一過程一直進行到已發現從源節點可達的所有節點為止。( 注意，這裡的前提是對二叉樹而言。dfs本身作為圖算法的一種，在後續我會單獨拉出來和回溯放一起講。)
如上圖二叉樹，它的通路順序為：
a-b-d-e-c-f-g
到這裡，我們思考一個問題？雖然我們用遞歸的方式根據dfs的思想順利完成了題目。但是這種方式的缺點卻顯而易見。因為在遞歸中，如果層級過深，我們很可能儲存過多的臨時變量，導緻棧溢出。這也是為什麼我們一般不在背景代碼中使用遞歸的原因。如果不了解，下面我們詳細說明：
事實上，函數調用的參數是通過棧空間來傳遞的，在調用過程中會占用線程的棧資源。而遞歸調用，隻有走到最後的結束點後函數才能依次退出，而未到達最後的結束點之前，占用的棧空間一直沒有釋放，如果遞歸調用次數過多，就可能導緻占用的棧資源超過線程的最大值，進而導緻棧溢出，導緻程式的異常退出。
是以，我們引出下面的話題：如何将遞歸的代碼轉化成非遞歸的形式。這裡請記住，基本所有的遞歸轉非遞歸，都可以通過棧來進行實作。非遞歸的dfs，代碼如下：
上面的代碼，唯一需要強調的是，為什麼需要先右後左壓入資料？是因為我們需要将先通路的資料，後壓入棧（請思考棧的特點）。
如果不了解代碼，請看下圖：
說明：
1：首先将a壓入棧
2：a彈棧，将c、b壓入棧（注意順序）
3：b彈棧，将e、d壓入棧
4,5：d、e、c彈棧，将g、f壓入棧
6：f、g彈棧
至此，非遞歸的 dfs 就講解完畢了。那如何通過非遞歸dfs的方式，來對本題求解呢？相信已經很簡單了，這個下去自己試試就ok了了。
在上文中，我們通過例題學習了二叉樹的dfs（深度優先搜尋），其實就是沿着一個方向一直向下周遊。那我們可不可以按照高度一層一層的通路樹中的資料呢？當然可以，就是本節中我們要講的bfs（寬度優先搜尋），同時也被稱為廣度優先搜尋。
第102題：給定一個二叉樹，傳回其按層次周遊的節點值。（即逐層地，從左到右通路所有節點）。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
/ \
9 20
15 7
傳回其層次周遊結果：[[3],[9,20],[15,7]]
bfs，廣度/寬度優先。說白了就是從上到下，先把每一層周遊完之後再周遊一下一層。假如我們的樹如下：
按照bfs，通路順序如下：
a->b->c->d->e->f->g
了解了bfs，我們開始對本題進行分析。同樣，我們先考慮本題的遞歸解法。想到遞歸，我們一般先想到dfs。我們可以對該二叉樹進行先序周遊（根左右的順序），同時，記錄節點所在的層次level，并且對每一層都定義一個數組，然後将通路到的節點值放入對應層的數組中。
假設給定二叉樹為[3,9,20,null,null,15,7]，圖解如下：
根據分析，代碼如下：
上面的解法，其實相當于是用dfs的方法實作了二叉樹的bfs。那我們能不能直接使用bfs的方式進行解題呢？當然可以。我們使用queue的資料結構。我們将root節點初始化進隊列，通過消耗尾部，插入頭部的方式來完成bfs。
具體步驟如下圖：
根據分析，完成代碼：
bst是二叉搜尋樹，很重要。bst是二叉搜尋樹，很重要。bst是二叉搜尋樹，很重要。重要的事情說三遍。
第98題：給定一個二叉樹，判斷其是否是一個有效的二叉搜尋樹。
示例 1:
輸入:
1 4
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
根節點的值為 5 ，但是其右子節點值為 4 。
要驗證二叉搜尋樹，首先得知道啥是二叉搜尋樹。二叉搜尋樹（binary search tree），（又：二叉查找樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分别為二叉搜尋樹。
這裡強調一下子樹的概念：設t是有根樹，a是t中的一個頂點，由a以及a的所有後裔（後代）導出的子圖稱為有向樹t的子樹。具體來說，子樹就是樹的其中一個節點以及其下面的所有的節點所構成的樹。比如下面這就是一顆二叉搜尋樹：
下面這兩個都不是：
圖中4節點位置的數值應該大于根節點
圖中3節點位置的數值應該大于根節點
回到題目，那我們如何來驗證一顆二叉搜尋樹？首先看完題目，我們很容易想到 周遊整棵樹，比較所有節點，通過 左節點值<節點值，右節點值＞節點值 的方式來進行求解。但是這種解法是錯誤的，因為對于任意一個節點，我們不光需要左節點值小于該節點，并且左子樹上的所有節點值都需要小于該節點。（右節點一緻）是以我們在此引入上界與下界，用以儲存之前的節點中出現的最大值與最小值。
代碼其實很簡單：
難就難在，可能大家看不懂這個遞歸！沒事，祭出大殺器：
這裡需要強調的是，在每次遞歸中，我們除了進行左右節點的校驗，還需要與上下界進行判斷。其餘的就很簡單了。
在上文中，我們學習了二叉搜尋樹。那我們如何在二叉搜尋樹中查找一個元素呢？
第700題：給定二叉搜尋樹（bst）的根節點和一個值。你需要在bst中找到節點值等于給定值的節點。傳回以該節點為根的子樹。如果節點不存在，則傳回 null。
例如，給定二叉搜尋樹:
搜尋: 2
你應該傳回如下子樹:
在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該傳回 null。
先複習一下，二叉搜尋樹（bst）的特性：
1.若它的左子樹不為空，則所有左子樹上的值均小于其根節點的值
2.若它的右子樹不為空，則所有右子樹上的值均大于其根節點得值
3.它的左右子樹也分别為二叉搜尋樹
如下圖就是一棵典型的bst：
現在我們來看題，假設目标值為 val。根據bst的特性，我們可以很容易想到查找過程（上面的驗證比查找稍難一點）：
如果val小于目前結點的值，轉向其左子樹繼續搜尋；
如果val大于目前結點的值，轉向其右子樹繼續搜尋；
如果已找到，則傳回目前結點。
很簡單，不是嗎？然後我們可以給出疊代和遞歸兩種解法（給個java的吧！）：
查找有了，下面自然就要講删除。（為啥說我要着重墨在bst上面，因為bst這兩年在面試時非常高頻。面試官不可能說問你一個普通二叉樹的題目，要麼就是問堆，要麼就是問bst，或者就直接dfs考察回溯。）
第450題：給定一個二叉搜尋樹的根節點 root 和一個值 key，删除二叉搜尋樹中的 key 對應的節點，并保證二叉搜尋樹的性質不變。傳回二叉搜尋樹（有可能被更新）的根節點的引用。
一般來說，删除節點可分為兩個步驟：
首先找到需要删除的節點；
如果找到了，删除它。
說明：要求算法時間複雜度為 o(h)，h 為樹的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
3 6
/ \ \
2 4 7
給定需要删除的節點值是 3，是以我們首先找到 3 這個節點，然後删除它。
一個正确的答案是 [5,4,6,2,null,null,7], 如下圖所示。
4 6
/ \
2 7
另一個正确答案是 [5,2,6,null,4,null,7]。
2 6
\ \
如果你看到了這裡，相信肯定知道bst是個啥了。是以直接分析題目。我們要删除bst的一個節點，首先需要找到該節點。而找到之後，會出現三種情況。
待删除的節點左子樹為空，讓待删除節點的右子樹替代自己。
待删除的節點右子樹為空，讓待删除節點的左子樹替代自己。
如果待删除的節點的左右子樹都不為空。我們需要找到比目前節點小的最大節點（前驅），來替換自己
或者比目前節點大的最小節點（後繼），來替換自己。
分析完畢，直接上代碼。這裡我們給出通過後繼節點來替代自己的方案（可以自行實作另一種方案）：
bst講解完了。上面也說了，别人考察我們肯定是考察特殊的。那二叉樹裡還有啥特殊的東東嘞？平衡二叉樹算是一個。
**第110題：給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：**
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。
給定二叉樹 [3,9,20,null,null,15,7]
傳回 true 。
示例 2:
給定二叉樹 [1,2,2,3,3,null,null,4,4]
3 3
4 4
傳回 false 。
題其實是一道很簡單的題，主要是拿來複習一下高度。我們想判斷一棵樹是否滿足平衡二叉樹，無非就是判斷目前結點的兩個孩子是否滿足平衡，同時兩個孩子的高度差是否超過1。那隻要我們可以得到高度，再基于高度進行判斷即可。
這裡唯一要注意的是，當我們判定其中任意一個節點如果不滿足平衡二叉樹時，那說明整棵樹已經不是一顆平衡二叉樹，我們可以對其進行阻斷，不需要繼續遞歸下去。
然後還有一個初學者容易懵逼的：
這玩意，并不是平衡二叉樹。上代碼：
還有啥特殊的，要撈出來講一講的？
第222題：給出一個完全二叉樹，求出該樹的節點個數。
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含 1~ 2h 個節點。
2 3
/ \ /
4 5 6
輸出: 6
老樣子，我們得說說啥是完全二叉樹。完全二叉樹由滿二叉樹引出，先來了解一下什麼是滿二叉樹。如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。（二叉樹的度代表某個結點的孩子或者說直接後繼的個數，這個在上面已經說過了。對于二叉樹而言，1度是隻有一個孩子或者說單子樹，2度是有兩個孩子或者說左右子樹都有。）
那什麼又是完全二叉樹呢：如果二叉樹中除去最後一層節點為滿二叉樹，且最後一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。比如下面這顆：
這個就不是：
上面做了這麼多題了，你應該能想到我要說啥 --- 遞歸。二叉樹的題目基本上都可以遞歸求解。
但是很明顯，出題者肯定不是要這種答案。因為這種答案和完全二叉樹一毛錢關系都沒有。是以我們繼續思考。
由于題中已經告訴我們這是一顆完全二叉樹，我們又已知了完全二叉樹除了最後一層，其他層都是滿的，并且最後一層的節點全部靠向了左邊。那我們可以想到，可以将該完全二叉樹可以分割成若幹滿二叉樹和完全二叉樹，滿二叉樹直接根據層高h計算出節點為2^h-1，然後繼續計算子樹中完全二叉樹節點。那如何分割成若幹滿二叉樹和完全二叉樹呢？對任意一個子樹，周遊其左子樹層高left，右子樹層高right，相等左子樹則是滿二叉樹，否則右子樹是滿二叉樹。這裡可能不容易了解，我們看圖。
假如我們有樹如下：
我們看到根節點的左右子樹高度都為3，那麼說明左子樹是一顆滿二叉樹。因為節點已經填充到右子樹了，左子樹必定已經填滿了。是以左子樹的節點總數我們可以直接得到，是2^left - 1，加上目前這個root節點，則正好是2^3，即 8。然後隻需要再對右子樹進行遞歸統計即可。
那假如我們的樹是這樣：
我們看到左子樹高度為3，右子樹高度為2。說明此時最後一層不滿，但倒數第二層已經滿了，可以直接得到右子樹的節點個數。同理，右子樹節點+root節點，總數為2^right，即2^2。再對左子樹進行遞歸查找。
根據分析，得出代碼：
該講的都講了，突然想到忘了一個經典操作 - 剪枝。迅速補上！非常重要！這裡額外說一點，就本人而言，對這個操作以及其衍化形式的使用會比較頻繁。因為我是做反欺詐的，機器學習裡有一個概念叫做決策樹，那如果一顆決策樹完全生長，就會帶來比較大的過拟合問題。因為完全生長的決策樹，每個節點隻會包含一個樣本。是以我們就需要對決策樹進行剪枝操作，來提升整個決策模型的泛化能力... 聽不懂也沒關系，簡單點講，就是我覺得這個很重要，或者每道算法題都很重要。如果你在工作中沒有用到，不是說明算法不重要，而可能是你還不夠重要。
第814題：給定二叉樹根結點 root ，此外樹的每個結點的值要麼是 0，要麼是 1。傳回移除了所有不包含 1 的子樹的原二叉樹。
( 節點 x 的子樹為 x 本身，以及所有 x 的後代。)
示例1:
輸入: [1,null,0,0,1]
輸出: [1,null,0,null,1]
解釋:
隻有紅色節點滿足條件“所有不包含 1 的子樹”。
右圖為傳回的答案。
示例2:
輸入: [1,0,1,0,0,0,1]
輸出: [1,null,1,null,1]
示例3:
輸入: [1,1,0,1,1,0,1,0]
輸出: [1,1,0,1,1,null,1]
說明:
給定的二叉樹最多有 100 個節點。
每個節點的值隻會為 0 或 1 。
還是先解釋一下，啥是剪枝：假設有一棵樹，最上層的是root節點，而父節點會依賴子節點。如果現在有一些節點已經标記為無效，我們要删除這些無效節點。如果無效節點的依賴的節點還有效，那麼不應該删除，如果無效節點和它的子節點都無效，則可以删除。剪掉這些節點的過程，稱為剪枝，目的是用來處理二叉樹模型中的依賴問題。
說了好多遍了，二叉樹的問題，大多都可以通過遞歸進行求解。直接分析。假設我們有二叉樹如下：[0,1,0,1,0,0,0,0,1,1,0,1,0]：
長這樣：
剪枝之後是這樣：
剪什麼大家應該都能了解。那關鍵是怎麼剪？過程也很簡單，在遞歸的過程中，如果目前結點的左右節點皆為空，且目前結點為0，我們就将目前節點剪掉即可。
其實很簡單，直接看代碼：
二叉樹入門整合系列篇到這裡就完事了，相信大家如果可以完整看完，一定會有所收獲。但是呢，其實大家可以看到，上面的系列還有很多内容沒有講。比如很核心的一塊dfs和回溯。這些都會在後面出單獨的系列進行講解，希望大家多多支援！
今天的整合篇去除了之前的一些備援内容，對部分圖解也進行了重構，熬夜整合，猝死邊緣。