Binary Tree Maximum Path Sum Solutions in C++

// Source : https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
// Author : Hao Chen
// Date   : 2014-10-10



#include <iostream>
#include <algorithm>
using namespace std;


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//The solution is quite simple can be explained by itself
int maxPathSum(TreeNode *root, int& maxSum ) {

    if (NULL == root) return 0;

    //get the maxPathSum for both left and right branch
    int left  = maxPathSum(root->left,  maxSum);
    int right = maxPathSum(root->right, maxSum);

    // The max sum could be one of the following situations:
    //    1) root + left
    //    2) root + right
    //    3) root
    //    4) root + left + right   
    //
    // And the whole function need to return the the max of 1) 2) 3) 
    int val = root->val;
    int maxBranch = left > right ? max(left + val, val) : max(right + val, val);
    int m = max(left + right + val, maxBranch);

    maxSum = max(maxSum, m);

    return maxBranch;
}

int maxPathSum(TreeNode *root) {
    #define INT_MIN     (-2147483647 - 1)
    int maxSum = INT_MIN;
    maxPathSum(root, maxSum);
    return maxSum;
}

int main()
{
    TreeNode root(1);
    TreeNode left(2);
    TreeNode right(3);
    root.left = &left;
    root.right = &right;
    cout << maxPathSum(&root) << endl; 
    return 0;
}

#include <cstddef>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    int maxPathSum(TreeNode *root, int &maxSum) {
        if (!root) return 0;
        int leftMax = std::max(0, maxPathSum(root->left, maxSum));
        int rightMax = std::max(0, maxPathSum(root->right, maxSum));
        maxSum = std::max(maxSum, leftMax+rightMax+root->val);
        return root->val + std::max(leftMax, rightMax);
    }

public:
    int maxPathSum(TreeNode *root) {
        int maxSum = INT_MIN;
        maxPathSum(root, maxSum);
        return maxSum;
    }
};

/// Source : https://leetcode.com/problems/binary-tree-maximum-path-sum/
/// Author : liuyubobobo
/// Time   : 2019-08-09

#include <iostream>
#include <unordered_map>

using namespace std;


/// Two Pass DFS
/// Time Complexity: O(n)
/// Space Complexity: O(n)

/// 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 {

private:
    unordered_map<TreeNode*, int> map;
    int res = INT_MIN;

public:
    int maxPathSum(TreeNode* root) {

        dfs1(root);
        dfs2(root);
        return res;
    }

private:
    void dfs2(TreeNode* node){

        if(!node) return;
        res = max(res, node->val + max(0, map[node->left]) + max(0, map[node->right]));
        dfs2(node->left);
        dfs2(node->right);
    }

    int dfs1(TreeNode* node){

        int left = node->left ? dfs1(node->left) : 0;
        int right = node->right ? dfs1(node->right) : 0;
        return map[node] = node->val + max(0, max(left, right));
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/binary-tree-maximum-path-sum/
/// Author : liuyubobobo
/// Time   : 2019-08-09

#include <iostream>
#include <unordered_map>

using namespace std;


/// One Pass DFS
/// Time Complexity: O(n)
/// Space Complexity: O(h)

/// 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 {

private:
    int res = INT_MIN;

public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }

private:
    int dfs(TreeNode* node){

        int left = node->left ? dfs(node->left) : 0;
        int right = node->right ? dfs(node->right) : 0;

        res = max(res, node->val + max(0, left) + max(0, right));

        return node->val + max(0, max(left, right));
    }
};


int main() {

    return 0;
}