Outline:

• 二叉樹的遍歷

• 前序遍歷非遞歸方法

• 前序遍歷分治法

• 遍歷方法與分治法

• Maximum Depth of Binary Tree

• Balanced Binary Tree

• 二叉樹的最大路徑和 (root->leaf)

• Binary Tree Maximum Path Sum II (root->any)

• Binary Tree Maximum Path Sum (any->any)

• 二叉查找樹

• Validate Binary Search Tree

• Binary Search Tree Iterator

• 二叉樹的寬度優(yōu)先搜索

• Binary Tree Level-Order Traversal

1.二叉樹的遍歷

這個應(yīng)該是二叉樹里面最基本的題了，但是在面試過程中，不一定會考遞歸的方式，很有可能會讓你寫出非遞歸的方法，應(yīng)該直接把非遞歸的方法背下來。這里我就不多說了，直接把中序遍歷的非遞歸方法貼出來吧，最后再加入一個分治法。

非遞歸方法（C++）：

分治法（Java）：

這兩種方法也是比較直觀的，前一個比較基礎(chǔ)，我就不詳細敘述了，但是分治法是值得重點說一說的。前面的遍歷的方法是需要對每一個點進行判斷和處理的，根據(jù)DFS進入到每一個節(jié)點，然后操作；但是使用分治法的話，就不需要考慮那么多，分治法的核心思想就是把一個整體的問題分為多個子問題來考慮，也就是說：每一個子問題的操作方法都是一樣的，子問題的解是可以合并為原問題的解的（這里就是和動態(tài)規(guī)劃、貪心法不一樣的地方）。

所以使用分治法的話，就不需要對每個節(jié)點都進行判斷，不管左右子樹的情況（是否存在），直接進行求解，最后把它們合并起來。之前聽課的時候老師也說過分治法就像一個女王大人，處于root的位置，然后派了兩位青蛙大臣去處理一些事物，女王大人只需要管好自己的val是多少，然后把兩個大臣的反饋直接加起來就可以了。個人認為分治法算是比較接近普通人思維的一種方法了。

2. 遍歷方法與分治法

遍歷方法其實在我經(jīng)過之前各種刷題套模板后算是能夠熟悉掌握了，所謂“雖不知其內(nèi)涵，但知其模板”的境界，今天這個總結(jié)，確實幫助不少。直接承接了上面所說的兩種思考。接下來我就直接用題解來分析一下：

2.1 Maximum Depth of Binary Tree

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的距離。

樣例

給出一棵如下的二叉樹:

 1 / \ 2   3   / \  4   5

這個二叉樹的最大深度為3

這個題目要是在面試的時候面到，那必須一分鐘內(nèi)寫出來，因為如果考慮分治法的話，就是一個簡單的DFS，代碼如下（Java）：

就是遞歸查看左右兩邊最大的深度，然后返回就可以。這個思路也比較簡單，我就不多說了。

接下來再來一個題目：

2.2 Balanced Binary Tree

給定一個二叉樹,確定它是高度平衡的。對于這個問題,一棵高度平衡的二叉樹的定義是：一棵二叉樹中每個節(jié)點的兩個子樹的深度相差不會超過1。 

樣例

給出二叉樹 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

A) 3 B) 3 / \ \ 9 20 20 / \ / \ 15 7 15 7

二叉樹A是高度平衡的二叉樹，但是B不是

這個題目思路也比較簡單，判斷一下左右子樹的高度差是否小于1，也是一個簡單的分治法問題。這里用一種比較高大上的方法，加入了一個ResultType類，代碼如下(Java)：

這里的ResultType保存了一個布爾值判斷子樹是否是平衡二叉樹，用一個最大深度表示該子樹的最大深度。然后在Divide階段，分別遞歸調(diào)用了左右子樹，之后判斷左右子數(shù)的最大深度差，并且判斷它們是否滿足平衡二叉樹，最后返回該子樹的最大深度。這個思考也是比較自然合理的。運用了這種調(diào)用類的方式來進行解答，頗有一番面向?qū)ο蟮母杏X，但是本人是不太喜歡這種方式的，因為不容易思考，還需要考慮很多自己不熟悉的地方，容易出錯。

接下來就是本篇文章的重要部分了。我要詳細描述一下二叉樹的最大路徑這個問題，記得有一次面試還面到過這個題，我也要把不同的情況寫出來。

先來最簡單的部分吧，給一棵二叉樹，找出從根節(jié)點出發(fā)到葉節(jié)點的路徑中，和最大的一條。這個就比較簡單了，直接遍歷整個樹，然后找到最大的路徑即可，這里我就不多說了，比較簡單。直接上題目吧：

2.3 （1）二叉樹的最大路徑和（root->leaf）

給一棵二叉樹，找出從根節(jié)點出發(fā)到葉節(jié)點的路徑中，和最大的一條。

樣例

給出如下的二叉樹：

 1 / \2   3

返回4。(最大的路徑為1→3)

就不需要多解釋了，我就直接把代碼貼出來（Java）:

2.4 Binary Tree Maximum Path Sum II (root -> any node)

給一棵二叉樹，找出從根節(jié)點出發(fā)的路徑中，和最大的一條。

這條路徑可以在任何二叉樹中的節(jié)點結(jié)束，但是必須包含至少一個點（也就是根了）。

樣例

給出如下的二叉樹：

 1 / \2   3

返回4。(最大的路徑為1→3)

這個就跟原始版的題目不一樣了，這里是從根到任意的節(jié)點，當然就不能采用原始問題的方法了，不然就是指數(shù)級別的復(fù)雜度了，這里就采用分治法了：

我們把分治的基本思想考慮進去：

1.遞歸的出口：當節(jié)點為null

2.Divide：分別對左右進行遞歸

3.Conquer：把得到的結(jié)果進行操作。

代碼如下(Java)：

這里有一個關(guān)鍵點，對于某一個節(jié)點來說，得到了左右子樹的和，這里我就要判斷是否加上子樹（這個部分就是和原始問題不一樣的地方，保證了是任意的節(jié)點），加上子樹的話是加左子樹還是右子樹，然后就能得到最大值了。這個題最大的關(guān)鍵還是在于不考慮左右子樹如何，就把他們派出去，得到結(jié)果以后再進行判斷。

2.5 Binary Tree Maximum Path Sum (any node -> any node)

給出一棵二叉樹，尋找一條路徑使其路徑和最大，路徑可以在任一節(jié)點中開始和結(jié)束（路徑和為兩個節(jié)點之間所在路徑上的節(jié)點權(quán)值之和）

樣例

給出一棵二叉樹：

 　　 1      / \     2   3

返回 6

這個題是上一個題目的升級版，這里求的就是任意兩個點的最大路徑和了。這樣的題其實就是從上面的題做了一個引申，不過之前的題必須考慮到root，所以就直接判斷左右子樹，而這里的話，就不需要考慮root了，所以問題就變成了一個“把每一個節(jié)點都當作root來考慮的問題”，這里是我自己的理解，可能我沒有表達清楚，也就是說，在每一步遞歸中，都需要把當前的root考慮為上一題中的root，然后來判斷哪個root得到的值是最大的。所以這里就需要增加一個全局變量來存儲了。代碼如下（C++）：

這個題關(guān)鍵就在于你要去判斷左右子樹的值是否會讓這一個小團的值變小，如果會，那就不加上左右子樹。最后的return也是一個關(guān)鍵的地方：因為不能有分叉，所以只返回一條路徑。

這兩個題目就是充分運用了分治的方法，還需要大家很深刻的去理解一下其中的內(nèi)涵，還是有一些需要思考的地方。

3. 二叉查找樹

個人認為在樹的題目中，最令人開心的就是二叉查找樹了，因為這種結(jié)構(gòu)本身就帶有一種光環(huán)：左子樹小于root，右子樹大于root，這方面的題只需要緊緊圍繞這個概念來做就可以。

3.1 Validate Binary Search Tree

給定一個二叉樹，判斷它是否是合法的二叉查找樹(BST)

一棵BST定義為：

• 節(jié)點的左子樹中的值要嚴格小于該節(jié)點的值。

• 節(jié)點的右子樹中的值要嚴格大于該節(jié)點的值。

• 左右子樹也必須是二叉查找樹。

• 一個節(jié)點的樹也是二叉查找樹。

樣例

一個例子：

 2 / \1   4   / \  3   5

上述這棵二叉樹序列化為 {2,1,4,#,#,3,5}.

看了這道題，我的第一個想法就是，判斷左邊最大的是否小于root，然后判斷右邊最小的是否大于root，然后遞歸去判斷。這個算法復(fù)雜度也比較高，可以貼上來給大家看看(C++)：

思路很簡單，就是找到左邊，然后找到最右的子樹，然后判斷root的val和它的關(guān)系，右子樹同理。之后遞歸往下進行判斷。

另一種方法就優(yōu)化了很多，用一個全局變量來存儲前一個指針，然后和當前的root比較，然后更新這個指針，代碼如下（C++）：

這個方法比較直觀，就是利用二叉樹的中序遍歷的方法，其中l(wèi)ast每次都更新為當前的節(jié)點。

關(guān)于二叉查找樹還有一個簡單的設(shè)計類的題，我就不多說了，直接上題吧：

3.2 Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)

• next() and hasNext() queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

  10 /    \1      11 \       \  6       12

我使用了隊列的方式來存儲二叉樹，然后進行相應(yīng)的操作，代碼如下(C++):

4. 二叉樹的寬度優(yōu)先搜索

終于到了我最喜歡的環(huán)節(jié)，傳說中的BFS，這個環(huán)節(jié)比較經(jīng)典，因為基本都可以套模板，不同的題只要加入一些不同的小trick就可以做出來，比如拓撲排序、圖遍歷啊等等，都需要用到BFS。前段時間在做我的圖像中像素的最大連通域的時候也用到了BFS，感覺比較常見，也相比于DFS的遞歸方法實現(xiàn)要容易思考。

4.1 Binary Tree Level-Order Traversal

給出一棵二叉樹，返回其節(jié)點值的層次遍歷（逐層從左往右訪問）

樣例

給一棵二叉樹 {3,9,20,#,#,15,7} ：

 3 / \9  20  /  \ 15   7

返回他的分層遍歷結(jié)果：

[  [3],  [9,20],  [15,7]]

有一種方法是判斷一下當前隊列的size，然后以此作為分層的判斷，之后進行size次循環(huán)，表示一層。代碼如下(C++):

還有一種方法是在每層遍歷完之后加入一個NULL指針作為分界的標準，當?shù)竭_NULL的時候，判斷q是否為空，不為空則表示當前層已經(jīng)遍歷結(jié)束，然后把當前層push_back到res中，然后清空；q為空則表示到達最后一層，記錄答案然后返回即可。代碼如下（C++）:

總結(jié)

本文對二叉樹和分治法進行了一個闡述。這次好好總結(jié)一下覺得有很多地方需要用到分治。我把以前寫的分治法的總結(jié)帖在下面吧：

一、概念

對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解決這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫做分治法。

二、分治法適用情況

1）問題的規(guī)?？s小到一定程度就可以容易解決

2）具有最子結(jié)構(gòu)的性質(zhì)（遞歸思想）

3）子問題的解可以合并為原問題的解（關(guān)鍵，否則為貪心法或者動態(tài)規(guī)劃法）

4）子問題是相互獨立的 ，子問題之間不包含公共的子子問題（重復(fù)解公共的子問題，一般用動態(tài)規(guī)劃法比較好）

三、分治法的步驟

step1 分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題

step2 解決：子問題規(guī)模較小而容易被解決則直接解決，否則遞歸地解各個子問題

step3 合并：將各個子問題的解合并為原問題的解

設(shè)計模式

Divide-and-Conquer(P)

     if |P|<=n0 then="" return="">

     將P分解為較小的字問題P1,P2,…,Pk

     for i<-1 to="">

          do Yi <- divide-and-conquer(pi)="">

     T <- merge(y1,y2,…,yk)="">

     return (T)