https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
這個題和 二叉樹的直徑 是很相似的捎拯。套路如出一轍撑蒜。
- 都是后續(xù)遍歷框架，即兒子節(jié)點需要向上匯報玄渗，父節(jié)點匯總信息座菠，再根據(jù)一定規(guī)則向上匯報。
- 遞歸返回的值并不是求解目標(biāo)藤树，而是由一個全局變量來記錄和更新求解目標(biāo)浴滴。后續(xù)遍歷完成后，全局變量的值就是求解目標(biāo)岁钓。
不同的是：二叉樹的直徑升略，每個節(jié)點向上匯報的是該節(jié)點的深度；本題屡限，每個節(jié)點向上匯報的是經(jīng)過該節(jié)點的深度方向上的最大和品嚣。
兩個題一起做體會一下。
思路：對于每個結(jié)點都有一條最大路徑钧大，那就是以這個結(jié)點為中間點翰撑，其左子樹的最大路徑+右子樹的最大路徑+root->val。要在整棵樹中找最大的一條這樣的路徑啊央，我們遍歷樹的所有節(jié)點不斷比較就OK了眶诈。
需要注意的是，因為結(jié)點可能是負(fù)數(shù)瓜饥，因此如果一顆子樹中最大的路徑還是負(fù)的話逝撬，那么就舍棄掉這半條路徑，返回0.
我的code:
*/
class Solution {
public:
int max_value = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return max_value;
}
int dfs(TreeNode* root) {
if (!root) {
return 0;
}
int left = dfs(root->left);
int right = dfs(root->right);
int answer = root->val;
if (left > 0) answer+= left;
if (right > 0) answer+= right;
max_value = max(max_value, answer);
int return_value = root->val;
return_value = max(return_value, root->val + left);
return_value = max(return_value, root->val + right);
return return_value;
}
}
答案的code更簡潔清晰：
class Solution {
public:
int res = INT_MIN;
int maxPathSum(TreeNode* root) {
solution(root);
return res;
}
int solution(TreeNode* root) {//函數(shù)的功能還是找到樹中的最大路徑乓土，框架完全沒變
if(root == NULL) return 0;
int Lmax = max(solution(root->left),0);
int Rmax = max(solution(root->right),0);
res = max(res, root->val + Lmax + Rmax);//填這一句
return max(Lmax, Rmax) + root->val;
}
}
多說一句宪潮，二叉樹的最矮公共祖先，也是后續(xù)遍歷框架趣苏，兒子需要向上匯報狡相，父親來匯總。那個題的遞歸求解目標(biāo)就是最終目標(biāo)拦键，只不過是谣光，兒子向上匯報的東西和父親匯總的規(guī)則檩淋，比較難想到芬为。
