題目
給定一個(gè)二叉樹(shù)，找出其最大深度。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：
給定二叉樹(shù) [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
思路
BFS廣度優(yōu)先搜索，使用雙端隊(duì)列deque（因?yàn)樾阅鼙攘硗鈨煞NQueue好得多），在大循環(huán)內(nèi)對(duì)二叉樹(shù)的每個(gè)層做一次遍歷，range(len(queue))使只遍歷當(dāng)前的層，每次大循環(huán)ans加1。由于每個(gè)節(jié)點(diǎn)僅訪問(wèn)一次，所以時(shí)間復(fù)雜度O(n)
代碼
import
collections
class
Solution
:
def
maxDepth
(
self
,
root
:
TreeNode
)
-
>
int
:
if
not
root
:
return
0
queue
=
collections
.
deque
(
)
queue
.
append
(
root
)
ans
=
0
while
queue
:
ans
+=
1
for
_
in
range
(
len
(
queue
)
)
:
node
=
queue
.
popleft
(
)
if
node
.
left
:
queue
.
append
(
node
.
left
)
if
node
.
right
:
queue
.
append
(
node
.
right
)
return
ans
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
