Outline:

• 二叉樹(shù)的遍歷

• 前序遍歷非遞歸方法

• 前序遍歷分治法

• 遍歷方法與分治法

• Maximum Depth of Binary Tree

• Balanced Binary Tree

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

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

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

• 二叉查找樹(shù)

• Validate Binary Search Tree

• Binary Search Tree Iterator

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

• Binary Tree Level-Order Traversal

1.二叉樹(shù)的遍歷

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

非遞歸方法（C++）：

分治法（Java）：

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

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

2. 遍歷方法與分治法

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

2.1 Maximum Depth of Binary Tree

給定一個(gè)二叉樹(shù)，找出其最大深度。

二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的距離。

樣例

給出一棵如下的二叉樹(shù):

 1 / \ 2   3   / \  4   5

這個(gè)二叉樹(shù)的最大深度為3

這個(gè)題目要是在面試的時(shí)候面到，那必須一分鐘內(nèi)寫(xiě)出來(lái)，因?yàn)槿绻紤]分治法的話，就是一個(gè)簡(jiǎn)單的DFS，代碼如下（Java）：

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

接下來(lái)再來(lái)一個(gè)題目：

2.2 Balanced Binary Tree

給定一個(gè)二叉樹(shù),確定它是高度平衡的。對(duì)于這個(gè)問(wèn)題,一棵高度平衡的二叉樹(shù)的定義是：一棵二叉樹(shù)中每個(gè)節(jié)點(diǎn)的兩個(gè)子樹(shù)的深度相差不會(huì)超過(guò)1。 

樣例

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

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

二叉樹(shù)A是高度平衡的二叉樹(shù)，但是B不是

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

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

接下來(lái)就是本篇文章的重要部分了。我要詳細(xì)描述一下二叉樹(shù)的最大路徑這個(gè)問(wèn)題，記得有一次面試還面到過(guò)這個(gè)題，我也要把不同的情況寫(xiě)出來(lái)。

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

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

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

樣例

給出如下的二叉樹(shù)：

 1 / \2   3

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

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

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

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

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

樣例

給出如下的二叉樹(shù)：

 1 / \2   3

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

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

我們把分治的基本思想考慮進(jìn)去：

1.遞歸的出口：當(dāng)節(jié)點(diǎn)為null

2.Divide：分別對(duì)左右進(jìn)行遞歸

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

代碼如下(Java)：

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

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

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

樣例

給出一棵二叉樹(shù)：

 　　 1      / \     2   3

返回 6

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

這個(gè)題關(guān)鍵就在于你要去判斷左右子樹(shù)的值是否會(huì)讓這一個(gè)小團(tuán)的值變小，如果會(huì)，那就不加上左右子樹(shù)。最后的return也是一個(gè)關(guān)鍵的地方：因?yàn)椴荒苡蟹植妫灾环祷匾粭l路徑。

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

3. 二叉查找樹(shù)

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

3.1 Validate Binary Search Tree

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

一棵BST定義為：

• 節(jié)點(diǎn)的左子樹(shù)中的值要嚴(yán)格小于該節(jié)點(diǎn)的值。

• 節(jié)點(diǎn)的右子樹(shù)中的值要嚴(yán)格大于該節(jié)點(diǎn)的值。

• 左右子樹(shù)也必須是二叉查找樹(shù)。

• 一個(gè)節(jié)點(diǎn)的樹(shù)也是二叉查找樹(shù)。

樣例

一個(gè)例子：

 2 / \1   4   / \  3   5

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

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

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

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

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

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

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

我使用了隊(duì)列的方式來(lái)存儲(chǔ)二叉樹(shù)，然后進(jìn)行相應(yīng)的操作，代碼如下(C++):

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

終于到了我最喜歡的環(huán)節(jié)，傳說(shuō)中的BFS，這個(gè)環(huán)節(jié)比較經(jīng)典，因?yàn)榛径伎梢蕴啄０澹煌念}只要加入一些不同的小trick就可以做出來(lái)，比如拓?fù)渑判?、圖遍歷啊等等，都需要用到BFS。前段時(shí)間在做我的圖像中像素的最大連通域的時(shí)候也用到了BFS，感覺(jué)比較常見(jiàn)，也相比于DFS的遞歸方法實(shí)現(xiàn)要容易思考。

4.1 Binary Tree Level-Order Traversal

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

樣例

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

 3 / \9  20  /  \ 15   7

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

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

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

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

總結(jié)

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

一、概念

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

二、分治法適用情況

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

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

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

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

三、分治法的步驟

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

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

step3 合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解

設(shè)計(jì)模式

Divide-and-Conquer(P)

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

     將P分解為較小的字問(wèn)題P1,P2,…,Pk

     for i<-1 to="">

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

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

     return (T)