124. Binary Tree Maximum Path Sum

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.

For example: Given the below binary tree,

       1
      / \
     2   3

Return6.

Thoughts:

in top down order, for each node do:

1. calculate the current path sum, update the record

2. pass the larger branched sum value to the parent

Code:

/**
 * 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 {
    int answer;
public:
    int maxPathSum(TreeNode* root) {
        answer = INT_MIN;
        maxPathSumDown(root);   
        return answer;
    }

    int maxPathSumDown(TreeNode * cur){
        if(!cur) return 0;

        int left = max(0, maxPathSumDown(cur->left));
        int right = max(0, maxPathSumDown(cur->right));
        answer = max(answer, left + right + cur ->val);
        return max(left, right) + cur->val;
    }
};

Code without global variable

/**
 * 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 {
    int answer;
public:
    int maxPathSum(TreeNode* root) {
        answer = INT_MIN;
        maxPathSumDown(root);   
        return answer;
    }

    int maxPathSumDown(TreeNode * cur){
        if(!cur) return 0;

        int left = max(0, maxPathSumDown(cur->left));
        int right = max(0, maxPathSumDown(cur->right));
        answer = max(answer, left + right + cur ->val);
        return max(left, right) + cur->val;
    }
};

Code (Python)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    maxVal = float("-inf")
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxPathDown(root)
        return self.maxVal 

    def maxPathDown(self, cur):
        if not cur: 
            return 0
        left = max(0, self.maxPathDown(cur.left))
        right = max(0, self.maxPathDown(cur.right))
        self.maxVal = max(self.maxVal, left + right + cur.val)
        return max(left, right) + cur.val

Special Thanks to wei-bung for providing this solution