劍指Offer_程式設計題——二叉樹的深度
題目描述：
輸入一顆二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點(含根、葉結點)形成樹的一條路徑，最長路徑為樹的深度。
具體要求：
時間限制： C/C++ 1秒，其他語言2秒
空間限制： C/C++32M，其他語言64M
具體實作
背景知識介紹在開始做本題之前我們先給大家介紹**二叉樹樹的周遊：**
先序周遊、
中序周遊、
後序周遊以及
層次周遊。二叉樹的周遊（traversing binary tree）是指從根結點出發，按照某種次序依次通路二叉樹中所有的結點，使得每個結點被通路依次且僅被通路一次。
1、前序周遊，先檢查
根節點，然後遞歸周遊
左子樹和
右子樹2、中序周遊，先周遊
左子樹，然後檢查
根節點，最後周遊
右子樹3、後序周遊，先遞歸周遊
左右子樹，然後檢查
根節點4、層次周遊，從
第一層開始，
一層一層往下周遊
我們以
10,5,19,4,8,13,24為例，用動畫詳細介紹這四種周遊：
案例
1、前序周遊 前序周遊
a：輸出目前節點值10，然後輸出左子樹，最後輸出右子樹；
b、對于其左子樹來說，同樣以這樣的順序，則先輸出5，然後輸出左子樹4，最後輸出右子樹8；
c、對于其右子樹，同樣以這樣的順序，則先輸出19，然後輸出左子樹13，最後輸出右子樹24；
最終得到前序周遊輸出為：
10,5,4,8,19,13,24。 2、中序周遊 中序周遊
a：先輸出左子樹，然後輸出目前節點13，最後輸出右子樹；
b：對于其左子樹來說，同樣以這樣的順序，則先輸出左子樹16，然後輸出節點值22，最後輸出右子樹28；
c：對于其右子樹，同樣以這樣的順序，則先,輸出左子樹29，然後輸出節點值30，最後輸出右子樹43；
最終得到中序周遊輸出為：
13 16 22 28 29 30 43。我們發現
二叉查找樹的中序周遊輸出就是排序後的結果。是以二叉查找樹也叫二叉搜尋樹或者二叉排序樹。
3、後序周遊 後序周遊
a：先輸出左子樹，然後輸出右子樹，最後輸出節點值13
b：對于其左子樹來說，同樣以這樣的順序，則先輸出左子樹22，然後輸出右子樹16，最後輸出節點值29；
c：對于其右子樹，同樣以這樣的順序，則先,輸出左子樹43，然後輸出右子樹30，最後輸出節點值28
最終得到後序周遊輸出為：
13 22 16 29 43 30 28。 5、層次周遊 a：周遊第一層，輸出10
b：周遊第二層，輸出5,19
c：周遊第三層，輸出4,8,13,24
最終得到層次周遊輸出為： 10，5,19,4,8,13,24 。
不過雖然看起來過程很簡單，但是代碼實作卻不能像前面三種深度優先周遊方式那樣 直接使用遞歸，它更好的方式是借助一個具有 先入先出特點的隊列（隊列可參考隊列-C語言實作）。以三個節點為例，我們先将根節點入隊，然後分别入隊左右孩子節點，最後輸出隊列内容，那麼它的順序就是層次周遊的順序了。
注意：由于中序周遊和後序周遊中的動圖是.webp格式，知乎不支援該格式，是以重新找了相關的動圖，不過不妨礙中序周遊和後序周遊的了解。如果想看配套的動圖可以看這篇文章。
具體實作
本題主要是求二叉樹的深度，其實首先要進行二叉樹的周遊，本題可以通過先序周遊、層次周遊、還可以用作遞歸。具體實作如下：
1、首先我們進行層次周遊
import
代碼效果圖如圖所示：
正如我們之前的文章中提到，如果在牛客網中我們以上代碼可以直接編譯通過，因為它給我們定義了節點TreeNode，但如果在本地編譯器(IDEA)中，我們得自己定義該節點，具體實作如下：
public
2、接下來，我們用遞歸來解決該題，其實任意的二叉樹均可以看作root----left----right。具體實作如下：
public
代碼效果圖如圖所示：
找到左右子樹最大深度+1即可，遞歸的終止條件是空節點的深度是0。其實與我們剛才的遞歸算法很類似，具體用python實作如下：
class
代碼效果圖如圖所示：
用python實作TreeNode結構：
class
3、然後我們用先序周遊來解決該題。實際上線找右子樹的最大高度，再找左子樹的最大高度。當然我們也可以先左子樹進棧，然後右子樹進棧，也就是先找左子樹的最大高度，再找右子樹的最大高度。具體實作如下：
import
代碼效果圖如圖所示：
最後一種就是暴力法，具體實作如下：
public
代碼效果圖如圖所示：
總結
本道題主要考察二叉樹的深度，本題直截了當，思路清晰。很顯然考察的是二叉樹的四種周遊以及遞歸在二叉樹中的使用，我們之前的很多二叉樹的題目中，均用到了遞歸，是以，本題給出了四種解法來解決此題，并且在解題之前用動畫的形式詳細的為大家介紹了二叉樹的四種周遊方法。是以，我們在做題的時候，應該多次嘗試各種方法，擴充自己的思維，寫出優質的代碼。總之，我們要繼續加油，争取早日找到工作，Good Luck！！！
參考文獻
[1]動畫：二叉樹周遊的多種姿勢
[2]COSCHINA
[3]Chosen_Xxx