付費限定

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

更新於 2024/08/18閱讀時間約 5 分鐘

題目敘述

題目會給定一個二元樹的樹根結點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深度優先,站在遞迴角度,從上到下的視野來看這個問題。

raw-image

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

通則(General cases):
樹的最大深度 = 1 + Max(左子樹的深度, 右子樹的深度)
= 根結點貢獻的深度 1 + Max( 左子樹的深度, 右子樹的深度)


終止條件(Base case)
遇到空結點或者空樹回傳0 即可
因為不存在,也沒有東西自然也沒有深度可言


以行動支持創作者!付費即可解鎖
本篇內容共 2302 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 題目會給我們一個輸入陣列arr,起始點固定在索引為0的位置, 終點固定在索引為n-1的位置。 假設當下所在的索引位置為i,那麼每次移動的時候,可以跳到i-1,i+1,或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。 例如: 假設當下在i=3
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以左右位移的固定長度。 例如,假設 nums[i] = 3,那麼下一步可以移動到nums[i-3] 或 nums[i+3]這兩個格子點。 題目​會給定一個起始點start索引位置,請問我們能不能走到內部數值為0的格子點?
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以跳躍的最大長度。 題目保證始從最左邊的格子點出發開始跳,一定可以成功抵達終點,請問最少跳躍次數是說少? 題目的原文敘述 測試範例 Example 1: Input: nums = [2,3,1,1,4] Outp
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以跳躍的最大長度。 一開始從最左邊的格子點出發開始跳,請問可以成功抵達終點,也就是最右邊的格子點嗎? 如果可以,返回 True。 如果不行,返回False。 題目的原文敘述 測試範例 Example 1: In
題目敘述 題目會給我們一個房間陣列rooms,每個房間裡面擁有數量不等,可以打開其他房間的鑰匙。 每一道房間門預設都是鎖住的,只有0號房間的門一開始是打開的。 請問,從0號房間開始拿鑰匙,最終能不能打開所有房間的門? 題目的原文敘述 測試範例
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
題目敘述 題目會給我們一個輸入陣列arr,起始點固定在索引為0的位置, 終點固定在索引為n-1的位置。 假設當下所在的索引位置為i,那麼每次移動的時候,可以跳到i-1,i+1,或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。 例如: 假設當下在i=3
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以左右位移的固定長度。 例如,假設 nums[i] = 3,那麼下一步可以移動到nums[i-3] 或 nums[i+3]這兩個格子點。 題目​會給定一個起始點start索引位置,請問我們能不能走到內部數值為0的格子點?
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以跳躍的最大長度。 題目保證始從最左邊的格子點出發開始跳,一定可以成功抵達終點,請問最少跳躍次數是說少? 題目的原文敘述 測試範例 Example 1: Input: nums = [2,3,1,1,4] Outp
題目敘述 題目會給我們一個輸入陣列nums,每個元素值代表那個格子點可以跳躍的最大長度。 一開始從最左邊的格子點出發開始跳,請問可以成功抵達終點,也就是最右邊的格子點嗎? 如果可以,返回 True。 如果不行,返回False。 題目的原文敘述 測試範例 Example 1: In
題目敘述 題目會給我們一個房間陣列rooms,每個房間裡面擁有數量不等,可以打開其他房間的鑰匙。 每一道房間門預設都是鎖住的,只有0號房間的門一開始是打開的。 請問,從0號房間開始拿鑰匙,最終能不能打開所有房間的門? 題目的原文敘述 測試範例
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
你可能也想看
Google News 追蹤
Thumbnail
*合作聲明與警語: 本文係由國泰世華銀行邀稿。 證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務,定期定額(股)服務由國泰綜合證券提供。   剛出社會的時候,很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天,都會聽到各種市場動態、理財話題,像是:聯準會降息或是近期哪些科
Thumbnail
昨天自己又測試了一下,感覺還是有優化的空間,又做了一些細微調整,目前我認為這個版本非常強悍了。
Thumbnail
有一次在家裡整理東西時,我的貓嚇到我了。因為當時就只有我一個人在家,所以非常的安靜。那你可能會想,貓咪走路不都沒有聲音的嗎?沒錯,正因為牠們走路都沒有聲音所以才更嚇人,因為當時並不曉得貓咪從自己後方走過來,完全沒有腳步聲的狀況下,只聽到了一個聲音,那就是呼吸聲。當下聽到急促的呼吸聲也沒有聯想到是自己
Thumbnail
「醫師啊,我從前體檢的血糖好像有一點超標,算不算糖尿病?需要再驗嗎?我平時都沒有不舒服,應該沒關係吧!」一到診間坐下,中年大叔就開口詢問:「我應該是健康的胖子,雖然這顆肚子消不下來,不過假日都有出門散步運動,體力還不錯。」語畢,滿意地拍拍自己的肚子。
Thumbnail
l 政府的教育目的到底是什麼? l 錯誤的目的、心態導致後面一連串的錯誤 l 我們可以如何跨出去?
Thumbnail
民事案件:不動產「借名登記」問題多!借名登記探究(一)-內部關係 不動產借名登記契約是否有效?是否違反民法上強制及禁止規定?如若有效,則不動產借名登記契約的性質為何?是消極信託還是類推適用民法的委任契約條文?
Thumbnail
童文薰律師在童溫層節目中整理出蔡英文一魚多吃的記錄 我其實蠻意外,在童文薰律師揭露蔡英文論文原稿一魚多吃之後,御用媒體會真的當回事發報導洗白的;因為這真的不是一般人會關心的事。但《芋傳媒》還真的引用了一個臉書粉專:《翻譯有要緊》的貼文煞有介事的這麼做了。
Thumbnail
本所許健鈴律師主持【歡迎搭乘,喜麗詩號】,從李佳庭社工的《你不伸手,他會在這裡躺多久?:一個年輕社工的掙扎與淚水》,談談幾個跟街友相關的法律問題。
Thumbnail
●2017印尼電影【愛的所有格 Posesif】有一種愛叫佔有 (普特莉馬利諾 阿迪帕提多肯 葛莉瑟達阿嘉莎 奇可庫尼阿萬) 這張海報跟在HamiVedio付費頻道【愛的所有格 Posesif】的預告片,是讓我驚豔的。
Thumbnail
*合作聲明與警語: 本文係由國泰世華銀行邀稿。 證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務,定期定額(股)服務由國泰綜合證券提供。   剛出社會的時候,很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天,都會聽到各種市場動態、理財話題,像是:聯準會降息或是近期哪些科
Thumbnail
昨天自己又測試了一下,感覺還是有優化的空間,又做了一些細微調整,目前我認為這個版本非常強悍了。
Thumbnail
有一次在家裡整理東西時,我的貓嚇到我了。因為當時就只有我一個人在家,所以非常的安靜。那你可能會想,貓咪走路不都沒有聲音的嗎?沒錯,正因為牠們走路都沒有聲音所以才更嚇人,因為當時並不曉得貓咪從自己後方走過來,完全沒有腳步聲的狀況下,只聽到了一個聲音,那就是呼吸聲。當下聽到急促的呼吸聲也沒有聯想到是自己
Thumbnail
「醫師啊,我從前體檢的血糖好像有一點超標,算不算糖尿病?需要再驗嗎?我平時都沒有不舒服,應該沒關係吧!」一到診間坐下,中年大叔就開口詢問:「我應該是健康的胖子,雖然這顆肚子消不下來,不過假日都有出門散步運動,體力還不錯。」語畢,滿意地拍拍自己的肚子。
Thumbnail
l 政府的教育目的到底是什麼? l 錯誤的目的、心態導致後面一連串的錯誤 l 我們可以如何跨出去?
Thumbnail
民事案件:不動產「借名登記」問題多!借名登記探究(一)-內部關係 不動產借名登記契約是否有效?是否違反民法上強制及禁止規定?如若有效,則不動產借名登記契約的性質為何?是消極信託還是類推適用民法的委任契約條文?
Thumbnail
童文薰律師在童溫層節目中整理出蔡英文一魚多吃的記錄 我其實蠻意外,在童文薰律師揭露蔡英文論文原稿一魚多吃之後,御用媒體會真的當回事發報導洗白的;因為這真的不是一般人會關心的事。但《芋傳媒》還真的引用了一個臉書粉專:《翻譯有要緊》的貼文煞有介事的這麼做了。
Thumbnail
本所許健鈴律師主持【歡迎搭乘,喜麗詩號】,從李佳庭社工的《你不伸手,他會在這裡躺多久?:一個年輕社工的掙扎與淚水》,談談幾個跟街友相關的法律問題。
Thumbnail
●2017印尼電影【愛的所有格 Posesif】有一種愛叫佔有 (普特莉馬利諾 阿迪帕提多肯 葛莉瑟達阿嘉莎 奇可庫尼阿萬) 這張海報跟在HamiVedio付費頻道【愛的所有格 Posesif】的預告片,是讓我驚豔的。