https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

這個題和 二叉樹的直徑 是很相似的。套路如出一轍。

1. 都是后續(xù)遍歷框架，即兒子節(jié)點(diǎn)需要向上匯報，父節(jié)點(diǎn)匯總信息，再根據(jù)一定規(guī)則向上匯報。
2. 遞歸返回的值并不是求解目標(biāo)，而是由一個全局變量來記錄和更新求解目標(biāo)。后續(xù)遍歷完成后，全局變量的值就是求解目標(biāo)。

不同的是：二叉樹的直徑，每個節(jié)點(diǎn)向上匯報的是該節(jié)點(diǎn)的深度；本題，每個節(jié)點(diǎn)向上匯報的是經(jīng)過該節(jié)點(diǎn)的深度方向上的最大和。
兩個題一起做體會一下。

思路：對于每個結(jié)點(diǎn)都有一條最大路徑，那就是以這個結(jié)點(diǎn)為中間點(diǎn)，其左子樹的最大路徑+右子樹的最大路徑+root->val。要在整棵樹中找最大的一條這樣的路徑，我們遍歷樹的所有節(jié)點(diǎn)不斷比較就OK了。
需要注意的是，因?yàn)榻Y(jié)點(diǎn)可能是負(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ī)則，比較難想到。