image.png
先上代码
int maxPathSum(TreeNode* root) {
//Leetcode124:二叉树中的最大路径和
int max_sum = INT_MIN;
int res = helpSum(root, max_sum);
return max(res,max_sum);
}
int helpSum(TreeNode* root,int&max_sum){
if(root==nullptr) return 0; //边界值处理
int left_gain = helpSum(root->left, max_sum);
int right_gain = helpSum(root->right, max_sum);
//求最大值 舍弃负值 max（0，val）
//经过当前根节点
int pass_root = root->val + max(left_gain,0) + max(right_gain,0);
//根节点只作为路径之一，继续向上递归
int path_sum = root->val + max(0,max(left_gain,right_gain));
max_sum = max(max_sum,max(pass_root,path_sum));
return path_sum;
}
【思路】
二叉树相关的题首先想到递归
要计算最大路径和 与左右两边的数的最大路径和有关
image.png
有无法进行递归的情况 解决方法是 用另一个整数去记录全局最大值
我掉了的坑
全局最大值不仅仅是记录 根节点+左右两边路径和 这一种情况
也要记录 根节点+左边路径和 根节点+右边路径和
value还可能等于负数 负数要舍弃 用max(0,left)这样代码回精简一点
