class Solution {
    int res;
public:
    int maxPathSum(TreeNode* root) {
        if (!root) {
            return 0;
        }
        res = INT_MIN;
        helper(root);
        return res;
    }
    
    int helper(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int left_max = max(0, helper(root->left));
        int right_max = max(0, helper(root->right));
        res = max(res, left_max+right_max+root->val);
        return max(left_max, right_max) + root->val;
    }
};