[leetcode] 124. Binary Tree Maximum Path Sum : https://leetcode.com/problems/binary-tree-maximum-path-sum/

Binary Tree Maximum Path Sum.cc

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    int ans = 0;
    int maxNum = 0;
    int getAns(TreeNode* root){
        if(root == NULL) return 0;
        int now = root->val;
        maxNum = max(maxNum, now);
        
        int left = getAns(root->left);
        int right = getAns(root->right);
        
        int sum = max(now, now + left);
        sum = max(sum, now + right);
        ans = max(ans, sum);
        ans = max(ans, now + right + left);
        return max(sum, 0);
    }
    
    int maxPathSum(TreeNode* root) {
        ans = root->val;
        maxNum = root->val;
        getAns(root);
        return maxNum >= 0 ? ans : maxNum;
    }
};