一、二元樹最大路徑和
（一）概念
 |
| 可能的三種路徑解 |
這題是要求在二元樹中，最大的路徑和。上圖可知路徑解有三種型態，分別為單一解、單邊解、雙邊解。
- 單一解：可能發生在只有一個節點、只有一個正值節點或全部都是負值節點的情況。
- 單邊解：可能發生於一個單邊為正、另一個單邊為負的情況。
- 雙邊解：發生於兩邊路徑皆為正
由於是樹狀結構，故我們可以用深度優先搜尋 (Depth-First Search, DFS)來走遍所有的節點，回傳最大單一解，以及紀錄最大解。
（二）實作
 |
| 二元樹最大路徑和 程式碼 |
以上為二元樹最大路徑和程式碼，使用maxDFS()去做DFS和紀錄最大值max，回傳值為最大單一解。maxDFS是一個遞迴函式，有兩種選擇，一種為root == nullptr，這是最簡單的終止情況，也就是空樹時，回傳0；另一種root != nullptr，這使得遞迴繼續展開，分別先展開左子樹 (left subtree)，後再展開右子樹 (right subtree)，同時會獲得最大左/右單邊解，如果得到的單邊解為負數，則以0取代負值。接下來比較目前最大解max和雙邊解（左右單邊解+目前節點值）誰比較大，最後再回傳最大單邊解。
二、相關文章
請詳見LeetCode相關文章
留言
張貼留言