難度: Hard
目前下列解法的時間複雜度: O(n)
題目說明
給你一棵binary tree的圖,每個節點上有一個數字。
求在此圖上畫一條路徑,將路徑上節點的數字相加的最大值為何?
* 路徑需要至少1個節點
解法: divide and conquer
將一節點的每棵子樹視為一個子問題,並將路徑拆解成下列兩種:
1. 答案的路徑會經過該節點
2. 答案的路徑不會經過該節點
而 1. 代表此路徑是沿著子樹的某一節點延伸至該節點。主視角換為子節點,往子樹看去,該路徑一樣沿著子樹的某一節點延伸至該節點。
因此回傳值除了子樹的答案以外,還需要一個延子樹而上的路徑之最大數字加總值。
最後處理各種因數字可為負而導致的各種邊界問題。
source code