付費限定
之字形走法的最大長度 Longest ZigZag Path_Leetcode #1372_精選75
更新於 2024/08/18閱讀時間約 6 分鐘
題目敘述
題目會給我們一顆二元樹的根節點。請問在這棵樹中，之字型走法的路徑長度最大值是多少?
如果無解，請返回 零。
註:
之字型走法就是有一段路徑，都是由連續的 左右左右...，或者 右左右左...所構成的路徑。(看下方的測試範例會更清楚題目的定義)
測試範例
Example 1:
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1]
Output: 0
無解，返回0
約束條件
Constraints:
- The number of nodes in the tree is in the range
[1, 5 * 10^4].
結點總數目介於1 ~ 五萬 之間。
1 <= Node.val <= 100
每個節點值都介於1~100之間。
演算法 DFS從上到下，攜帶擺動的方向資訊與擺動長度。
這題的關鍵是之字型的擺動方向。
串接的時候，我們需要知道剛剛從上面下來的是向左走還是向右走，接著可以分析它的結構，再針對子樹進行參數更新，盡量去延長之字型的路徑。
- 當剛剛從上面往下的時候是向左走
以行動支持創作者！付費即可解鎖
本篇內容共 2613 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容，可能因為尚未登入，或沒有該房間的查看權限。
90會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
*合作聲明與警語：
本文係由國泰世華銀行邀稿。
證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務，定期定額(股)服務由國泰綜合證券提供。
剛出社會的時候，很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天，都會聽到各種市場動態、理財話題，像是：聯準會降息或是近期哪些科
128. Longest Consecutive Sequence 解題
#生活旅行seeingtheworld
雲林沒有雲林市，我還真的沒想過這個問題。不過，我想這就是longstay 好玩的地方，能發覺到你所不知道的事。
雲林為何沒有雲林呢？因為雲林在南投！雲林國小也在南投。奇特吧。
總之粗略了解就是，清朝時這區域原只有彰化和嘉義，「林杞埔」隨後在南投竹山
Longest Common Prefix : 回傳陣列中所有字串的最長共同前序(LCP)，也就是從最前面開始依序算起，所有字串都擁有的字元。
2022年12月安排了30天的日本行。這30天內，我想我應該吃了15家左右的各式各樣拉麵，鹽味、豚骨、味噌、雞骨等口味都有，這篇來跟大家分享，至今我光看照片都還會流口水、念念不忘的三碗拉麵。下次去日本，有機會我還會再去吃一回。
在多倫多除了麥當勞以外還有什麼能吃? 出發前朋友曾十分體貼地說要寄電鍋給我，以備我吃不慣漢堡薯條，到了當地，市區及百貨公司果然有世界各國料理，連鮮芋仙、麻辣鍋、Buffet都有，不過我最推薦Tim Hortons咖啡跟A&W漢堡店。想喝珍珠奶茶當然也有，只不過一杯500cc珍奶要價近台幣200元！
想在加拿大留久一點要不要辦理遊學呢？非疫情下，台人可免簽在加拿大六個月。持學生簽證的好處是可以節省交通費，部分景點有優惠，入境美國也不用再申辦ESTA(2022.10前適用)。由於加拿大可以合法吸食大麻，很多人都想知道呼麻到底有多嗨，跟電影裡演的一樣嗎，街上到處都有販售點，但建議結伴同行比較安全。
現在才發現我竟然沒有發一篇關於Petzl Zigzag 上升器的文，這麼好用的東西!!我竟然沒有開箱，不過拖到現在來介紹也是有一個好處，就是我有了大量的使用經驗，或許開啟箱起來更能有心得能分享。
我買的是 PLUS版本
現在我們所見的《說文解字》，作者是東漢許慎，當中的小篆字形，有人一生奉為圭臬，努力學習模仿，也有人說：「一些字有錯誤，不能全部相信。」
到底哪些可信，哪些不可信？真要區別得好好的個別詳細的考察才行。就字形來說，我們可以先做三件事。做完後基本上就可以區分哪些是許慎的問題，哪些字例的錯誤不能怪罪於許慎。
紐西蘭北島 New Zealand North Island，有一個很特別的地方，那裡沒什麼車、沒什麼人。若要前往這個地方，景色只能用 …
*合作聲明與警語：
本文係由國泰世華銀行邀稿。
證券服務係由國泰世華銀行辦理共同行銷證券經紀開戶業務，定期定額(股)服務由國泰綜合證券提供。
剛出社會的時候，很常在各種 Podcast 或 YouTube 甚至是在朋友間聊天，都會聽到各種市場動態、理財話題，像是：聯準會降息或是近期哪些科
128. Longest Consecutive Sequence 解題
#生活旅行seeingtheworld
雲林沒有雲林市，我還真的沒想過這個問題。不過，我想這就是longstay 好玩的地方，能發覺到你所不知道的事。
雲林為何沒有雲林呢？因為雲林在南投！雲林國小也在南投。奇特吧。
總之粗略了解就是，清朝時這區域原只有彰化和嘉義，「林杞埔」隨後在南投竹山
Longest Common Prefix : 回傳陣列中所有字串的最長共同前序(LCP)，也就是從最前面開始依序算起，所有字串都擁有的字元。
2022年12月安排了30天的日本行。這30天內，我想我應該吃了15家左右的各式各樣拉麵，鹽味、豚骨、味噌、雞骨等口味都有，這篇來跟大家分享，至今我光看照片都還會流口水、念念不忘的三碗拉麵。下次去日本，有機會我還會再去吃一回。
在多倫多除了麥當勞以外還有什麼能吃? 出發前朋友曾十分體貼地說要寄電鍋給我，以備我吃不慣漢堡薯條，到了當地，市區及百貨公司果然有世界各國料理，連鮮芋仙、麻辣鍋、Buffet都有，不過我最推薦Tim Hortons咖啡跟A&W漢堡店。想喝珍珠奶茶當然也有，只不過一杯500cc珍奶要價近台幣200元！
想在加拿大留久一點要不要辦理遊學呢？非疫情下，台人可免簽在加拿大六個月。持學生簽證的好處是可以節省交通費，部分景點有優惠，入境美國也不用再申辦ESTA(2022.10前適用)。由於加拿大可以合法吸食大麻，很多人都想知道呼麻到底有多嗨，跟電影裡演的一樣嗎，街上到處都有販售點，但建議結伴同行比較安全。
現在才發現我竟然沒有發一篇關於Petzl Zigzag 上升器的文，這麼好用的東西!!我竟然沒有開箱，不過拖到現在來介紹也是有一個好處，就是我有了大量的使用經驗，或許開啟箱起來更能有心得能分享。
我買的是 PLUS版本
現在我們所見的《說文解字》，作者是東漢許慎，當中的小篆字形，有人一生奉為圭臬，努力學習模仿，也有人說：「一些字有錯誤，不能全部相信。」
到底哪些可信，哪些不可信？真要區別得好好的個別詳細的考察才行。就字形來說，我們可以先做三件事。做完後基本上就可以區分哪些是許慎的問題，哪些字例的錯誤不能怪罪於許慎。
紐西蘭北島 New Zealand North Island，有一個很特別的地方，那裡沒什麼車、沒什麼人。若要前往這個地方，景色只能用 …