Problem

Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example input:
[1,2,3]
Output: 6
Explanation: The maximum sum path is [1,2,3].

Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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 max_sum = INT_MIN;
        maxPathSum(root, max_sum);
        return max_sum;
    }
private:
    int maxPathSum(TreeNode* root, int& max_sum) {
        if (!root) return 0;
        int left = maxPathSum(root->left, max_sum);
        int right = maxPathSum(root->right, max_sum);
        int sum = root->val;
        if (left > 0) sum += left;
        if (right > 0) sum += right;
        max_sum = max(max_sum, sum);
        return max(root->val, max(root ->val + left, root->val + right));
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    Solution solution;
    cout << solution.maxPathSum(root) << endl;
    return 0;
}