tft每日頭條

 > 圖文

 > 二叉樹的深度咋算

二叉樹的深度咋算

圖文 更新时间:2025-02-02 13:55:23

二叉樹的深度咋算(二叉樹的最大深度)1

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

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例:

給定二叉樹 [3,9,20,null,null,15,7]

二叉樹的深度咋算(二叉樹的最大深度)2

返回它的最大深度 3 。

二叉樹的深度咋算(二叉樹的最大深度)3

我們能想到的最簡單的方式估計就是遞歸了,也就是下面這個圖

二叉樹的深度咋算(二叉樹的最大深度)4

如果對遞歸不熟悉的話可以看下我前面講的關于複仇一個故事362,漢諾塔。下面我們來畫個圖來分析下

二叉樹的深度咋算(二叉樹的最大深度)5

看明白了上面的過程,代碼就容易多了,我們看下

二叉樹的深度咋算(二叉樹的最大深度)6

除了遞歸,我們還可能想到的就是BFS(寬度優先搜索算法(又稱廣度優先搜索)),他的實現原理就是一層層遍曆,統計一下總共有多少層,我們來畫個圖分析一下。

二叉樹的深度咋算(二叉樹的最大深度)7

一層一層往下走,統計總共有多少層,我們來看下代碼

二叉樹的深度咋算(二叉樹的最大深度)8

想到BFS我們一般會和DFS聯想到一起,DFS是深度優先搜索算法,我們先來看下代碼

二叉樹的深度咋算(二叉樹的最大深度)9

這裡使用了兩個棧,一個是存儲節點的,一個是存儲每個節點到根節點總共經過多少個節點(包含根節點和當前節點)。

如果喜歡這篇文章還可以關注微信公衆号“數據結構和算法”,查看更多的算法題

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关圖文资讯推荐

热门圖文资讯推荐

网友关注

Copyright 2023-2025 - www.tftnews.com All Rights Reserved