题解 | #二叉树的最大路径和#

/*
描述
给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树:
{1,2,3}
返回的结果为6
Main idea:
问题分解，求树的最大路径，递归树的节点
有三种可能：
最大路径经过该节点本身从左子树到右子树
最大路径经过节点本身向父节点发展
最大路径就是节点本身
*/

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        postOrder(root);
        return maxSum;
    }
    int postOrder(TreeNode* root) {
        if (!root) return 0;
        int left = postOrder(root->left);
        int right = postOrder(root->right);
        int current = root->val;
        if (left > 0) current += left;
        if (right > 0) current += right;
        maxSum = max(maxSum, current);      // 最大路径是否是经过该节点本身从左子树到右子树或最大路径就是节点本身
        return max(root->val, max(left, right) + root->val);    // 最大路径经过节点本身向父节点发展
    }
private:
    int maxSum = INT_MIN;
};