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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    auto dfs(TreeNode* node){
        if(node==NULL)return 0;                        //节点为空则取0
        int lsum=dfs(node->left);                      //递归左路径最大值
        int rsum=dfs(node->right);                     //递归右路径最大值
        sum=max(sum,lsum+rsum+node->val);              //路径最大值=左右路径最大值+val
        return max(0,max(lsum,rsum)+node->val);        //返回单段路径最大值，小于0则放弃此路径
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return sum;
    }
private:
    int sum=-1000;
};