付費限定
一題多解 二元樹的最大深度 Maximum Depth of Binary Tree_Leetcode 104精選75
題目敘述
題目會給定一個二元樹的樹根結點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 即可。
因為不存在，也沒有東西，自然也沒有深度可言。
以行動支持創作者！付費即可解鎖
本篇內容共 2302 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容，可能因為尚未登入，或沒有該房間的查看權限。
92會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
「醫師，我最近做健檢，發現肝指數很高。」體態肥胖的年輕人拿出一疊報告，報告顯示有嚴重脂肪肝。
「根據各種檢查，你的肝指數超標應該與體重過重、脂肪肝有關。」醫師說。
「脂肪肝會怎樣嗎？」年輕人問。
「千萬別小看肥胖對健康的危害！脂肪肝也會造成肝炎，甚至肝癌喔。」
會考慮減重手術的患者大多是考量
上禮拜三段考複習，出了線上習題讓學生在課堂練習，我也頭一次有時間能夠好好檢討這些額外習題。
其中有一題是出自100第一次基測（正巧就是我考的那一年），主要考圓周角與平行截角的概念。有學生在練習時有問我這題，我也給了許多提示與引導，讓他能順利完成。（如筆記中的法1）
前言
如文章的封面圖片1/2~1/27總共有幾天呢?
如果你的答案是25天，那務必把這個日期的地雷搞懂
種樹問題計算
題目
一條路有50公尺，每10公尺種一棵樹，請問總共種了幾顆樹?
這時就會直覺，阿不就是50/10=5，總共種了5顆樹!!
但其實大錯特錯哦❌
2024/03/30
斷頭樹沒有支點可以丟，而且長的一團亂非常茂密，非常難投擲豆袋，不小心豆袋就會卡在樹上。
這時候有兩個選擇，一個是繞住主幹的上方固定點，一個是投擲過最上方的基部固定點，但對於斷頭樹來說還是很難進行最上方徒長枝的修剪。
雖然我們知道斷頭修剪不好，但往往因為修剪預算不足
題目敘述
給定一個正整數n，請找出最少用幾個完全平方數，可以讓他們的總和為n?
例如 n=12，最少用3個完全平方數就可讓他們的總和為n，因為12 = 4 + 4 + 4
題目的原文敘述
測試範例
Example 1:
Input: n = 12
Output: 3
Explanat
題目敘述
題目會給我們一棵二元樹的根結點，要求我們找出哪一層擁有最大的水平元素和(Level-sum)?
題目的原文敘述
測試範例
Example 1:
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level
題目敘述
題目會給定一個二元樹的樹根結點Root node，要求我們計算這顆二元樹的最大深度是多少?
二元樹的深度的定義:
從根結點到葉子結點的最大路徑長度。
題目的原文敘述
約束條件
Constraints:
The number of nodes in the tree is
「醫師，我最近做健檢，發現肝指數很高。」體態肥胖的年輕人拿出一疊報告，報告顯示有嚴重脂肪肝。
「根據各種檢查，你的肝指數超標應該與體重過重、脂肪肝有關。」醫師說。
「脂肪肝會怎樣嗎？」年輕人問。
「千萬別小看肥胖對健康的危害！脂肪肝也會造成肝炎，甚至肝癌喔。」
會考慮減重手術的患者大多是考量
上禮拜三段考複習，出了線上習題讓學生在課堂練習，我也頭一次有時間能夠好好檢討這些額外習題。
其中有一題是出自100第一次基測（正巧就是我考的那一年），主要考圓周角與平行截角的概念。有學生在練習時有問我這題，我也給了許多提示與引導，讓他能順利完成。（如筆記中的法1）
前言
如文章的封面圖片1/2~1/27總共有幾天呢?
如果你的答案是25天，那務必把這個日期的地雷搞懂
種樹問題計算
題目
一條路有50公尺，每10公尺種一棵樹，請問總共種了幾顆樹?
這時就會直覺，阿不就是50/10=5，總共種了5顆樹!!
但其實大錯特錯哦❌
2024/03/30
斷頭樹沒有支點可以丟，而且長的一團亂非常茂密，非常難投擲豆袋，不小心豆袋就會卡在樹上。
這時候有兩個選擇，一個是繞住主幹的上方固定點，一個是投擲過最上方的基部固定點，但對於斷頭樹來說還是很難進行最上方徒長枝的修剪。
雖然我們知道斷頭修剪不好，但往往因為修剪預算不足
題目敘述
給定一個正整數n，請找出最少用幾個完全平方數，可以讓他們的總和為n?
例如 n=12，最少用3個完全平方數就可讓他們的總和為n，因為12 = 4 + 4 + 4
題目的原文敘述
測試範例
Example 1:
Input: n = 12
Output: 3
Explanat
題目敘述
題目會給我們一棵二元樹的根結點，要求我們找出哪一層擁有最大的水平元素和(Level-sum)?
題目的原文敘述
測試範例
Example 1:
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level
題目敘述
題目會給定一個二元樹的樹根結點Root node，要求我們計算這顆二元樹的最大深度是多少?
二元樹的深度的定義:
從根結點到葉子結點的最大路徑長度。
題目的原文敘述
約束條件
Constraints:
The number of nodes in the tree is