https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
这个题和 二叉树的直径 是很相似的。套路如出一辙。
- 都是后续遍历框架，即儿子节点需要向上汇报，父节点汇总信息，再根据一定规则向上汇报。
- 递归返回的值并不是求解目标，而是由一个全局变量来记录和更新求解目标。后续遍历完成后，全局变量的值就是求解目标。
不同的是：二叉树的直径，每个节点向上汇报的是该节点的深度；本题，每个节点向上汇报的是经过该节点的深度方向上的最大和。
两个题一起做体会一下。
思路：对于每个结点都有一条最大路径，那就是以这个结点为中间点，其左子树的最大路径+右子树的最大路径+root->val。要在整棵树中找最大的一条这样的路径，我们遍历树的所有节点不断比较就OK了。
需要注意的是，因为结点可能是负数，因此如果一颗子树中最大的路径还是负的话，那么就舍弃掉这半条路径，返回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) {//函数的功能还是找到树中的最大路径，框架完全没变
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;
}
}
多说一句，二叉树的最矮公共祖先，也是后续遍历框架，儿子需要向上汇报，父亲来汇总。那个题的递归求解目标就是最终目标，只不过是，儿子向上汇报的东西和父亲汇总的规则，比较难想到。
