一題多解 二元樹的最大深度 Maximum Depth of Binary Tree_Leetcode 104精選75

Luke Richardson on Unsplash

題目敘述

題目會給定一個二元樹的樹根結點Root node，要求我們計算這顆二元樹的最大深度是多少?

二元樹的深度的定義:

從根結點到葉子結點的最大路徑長度。

題目的原文敘述

約束條件

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].

結點總數目介於0~ 一萬之間。

題目有可能會給我們一顆空樹喔( 0 個節點的樹 )，請注意邊界條件的處理！

• -100 <= Node.val <= 100

每個結點的結點值介於-100 ~ 100 之間。

演算法 DFS 深度優先探索

遇事不決問周瑜 (誤 XD)

假如遇到圖論題目沒有特別想法的話，先聯想到DFS深度優先探索或BFS廣度優先探索，這兩個可以說是圖論演算法最泛用的模板，也是更進階圖論演算法的源頭。

我們先試著從DFS深度優先，站在遞迴角度，從上到下的視野來看這個問題。

抽象的想，二元樹可以用下列的模型來描述

通則(General cases):

樹的最大深度 = 1 + Max(左子樹的深度, 右子樹的深度)

= 根結點貢獻的深度 1 + Max( 左子樹的深度， 右子樹的深度)

終止條件(Base case)

遇到空結點或者空樹，回傳0 即可。

因為不存在，也沒有東西，自然也沒有深度可言。