給定一個二叉樹,找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定二叉樹 [3,9,20,null,null,15,7]
返回它的最大深度 3 。
我們能想到的最簡單的方式估計就是遞歸了,也就是下面這個圖
如果對遞歸不熟悉的話可以看下我前面講的關于複仇一個故事362,漢諾塔。下面我們來畫個圖來分析下
看明白了上面的過程,代碼就容易多了,我們看下
除了遞歸,我們還可能想到的就是BFS(寬度優先搜索算法(又稱廣度優先搜索)),他的實現原理就是一層層遍曆,統計一下總共有多少層,我們來畫個圖分析一下。
一層一層往下走,統計總共有多少層,我們來看下代碼
想到BFS我們一般會和DFS聯想到一起,DFS是深度優先搜索算法,我們先來看下代碼
這裡使用了兩個棧,一個是存儲節點的,一個是存儲每個節點到根節點總共經過多少個節點(包含根節點和當前節點)。
如果喜歡這篇文章還可以關注微信公衆号“數據結構和算法”,查看更多的算法題
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!