gistfile1.txt

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


class Solution {
public:
    int maxPathSum(TreeNode* root) {
        return max_path(root, -1000);
    }

private:
    int max_path(TreeNode* root, int max_path_previous)
    {
        if (root == nullptr) return -1000;

        auto max_path_children = std::max(
            max_path(root->left, max_path_previous),
            max_path(root->right, max_path_previous));
        auto left_val = root->left ? root->left->val : -1000;
        auto right_val = root->right ? root->right->val : -1000;
        auto new_root_val = std::max({
                root->val,
                root->val + left_val,
                root->val + right_val,
            });
        auto max_root_path = std::max(new_root_val, root->val + left_val + right_val);
        root->val = new_root_val;

        return std::max(max_path_children, max_root_path);
    }
};