付費限定
之字形走法的最大長度 Longest ZigZag Path_Leetcode #1372_精選75
閱讀時間約 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從上到下，攜帶擺動的方向資訊與擺動長度。
這題的關鍵是之字型的擺動方向。
串接的時候，我們需要知道剛剛從上面下來的是向左走還是向右走，接著可以分析它的結構，再針對子樹進行參數更新，盡量去延長之字型的路徑。
- 當剛剛從上面往下的時候是向左走
Support the creator with action! Pay to unlock
本篇內容共 2613 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整You currently cannot view the following content, possibly because you are not logged in or do not have permission to view the room.
82會員
417Content count
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
重點摘要：
1.9 月降息 2 碼、進一步暗示年內還有 50 bp 降息
2.SEP 上修失業率預期，但快速的降息速率將有助失業率觸頂
3.未來幾個月經濟數據將繼續轉弱，經濟復甦的時點或是 1Q25 季底附近
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎？
新版式整體視覺上「更加凸顯圖片」，為了搭配這次的更新，我們推出首次貼文策展 ❤️
使用貼文功能並完成這次的指定任務，還有機會獲得富士即可拍，讓你的美好回憶都可以用即可拍珍藏！
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，有一個很特別的地方，那裡沒什麼車、沒什麼人。若要前往這個地方，景色只能用 …
重點摘要：
1.9 月降息 2 碼、進一步暗示年內還有 50 bp 降息
2.SEP 上修失業率預期，但快速的降息速率將有助失業率觸頂
3.未來幾個月經濟數據將繼續轉弱，經濟復甦的時點或是 1Q25 季底附近
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎？
新版式整體視覺上「更加凸顯圖片」，為了搭配這次的更新，我們推出首次貼文策展 ❤️
使用貼文功能並完成這次的指定任務，還有機會獲得富士即可拍，讓你的美好回憶都可以用即可拍珍藏！
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，有一個很特別的地方，那裡沒什麼車、沒什麼人。若要前往這個地方，景色只能用 …