124. Binary Tree Maximum Path Sum

O(n) time

/**
 * 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 maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        helper(root, res);
        return res;
    }

    int helper(TreeNode *root, int &res) { // 以root结尾的最大和path的最大和
        if (!root) return 0;
        int l = max(0, helper(root->left, res)); // 如果返回的最大和是负数，则直接用0代替
        int r = max(0, helper(root->right, res));
        res = max(res, root->val + l + r); // 更新res
        return root->val + max(l, r); // 返回包括root在内的最大路径
    }
};