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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int ans=-9999999;
    int DFS(TreeNode* root)
    {
        if(root==NULL)
            return 0;
        int left=DFS(root->left);//左子树的最大路径和
        int right=DFS(root->right);//右子树的最大路径和
        int nowSum=root->val;//当前节点
        if(left>0) nowSum+=left;
        if(right>0) nowSum+=right;
        ans=max(ans,nowSum);
        return max(root->val,max(left,right)+root->val);
    }
        
        
    int maxPathSum(TreeNode* root) {
        // write code here
        ans=max(ans,DFS(root));
        return ans;
    }
};