前往
大廳
主題

[leetcode]124. Binary Tree Maximum Path Sum

♙♲⚙\~O_O~/⚙♲♙ | 2021-07-27 12:00:04 | 巴幣 12 | 人氣 161

題目: 124. Binary Tree Maximum Path Sum
難度: Hard
目前下列解法的時間複雜度: O(n)


題目說明

給你一棵binary tree的圖,每個節點上有一個數字。
求在此圖上畫一條路徑,將路徑上節點的數字相加的最大值為何?
* 路徑需要至少1個節點


解法: divide and conquer
將一節點的每棵子樹視為一個子問題,並將路徑拆解成下列兩種:
1. 答案的路徑會經過該節點
2. 答案的路徑不會經過該節點
而 1. 代表此路徑是沿著子樹的某一節點延伸至該節點。主視角換為子節點,往子樹看去,該路徑一樣沿著子樹的某一節點延伸至該節點。
因此回傳值除了子樹的答案以外,還需要一個延子樹而上的路徑之最大數字加總值。
最後處理各種因數字可為負而導致的各種邊界問題。


source code

創作回應

相關創作

更多創作