Binary Tree Maximum Path Sum

[Question]
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

[Analysis]
Define "maximum path to a given node" (MPN) as, the maximum path starts from a node under and ends at the node. The MPN(node) = max (node.val, node.val+MPN(node.left), node.val+MPN(node.right)).

The maximum path (P) via node N and with the sub-tree rooted by N will be,
         P(N) = (MPN( N.left )>0)?MPN(N.left):0 + N.val + (MPN(N.right)>0)?MPN(N.right):0)

So using post-order traversal, we can get all P(N) and find the maximum P(N).
                 

[Solution]


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSumToNode(TreeNode *root, int& cur_max) {
        if (root==NULL) return 0;
        int leftMax = maxPathSumToNode(root->left, cur_max);
        int rightMax= maxPathSumToNode(root->right, cur_max);
     
        int maxPathToRoot = max( max(leftMax+root->val, rightMax+root->val), root->val );
        int maxPathViaRoot = ((leftMax>0)?leftMax:0)
                            + root->val
                            + ((rightMax>0)?rightMax:0);
     
        if (maxPathViaRoot > cur_max) {
            cur_max = maxPathViaRoot;
        }
        return maxPathToRoot;
    }
 
    int maxPathSum(TreeNode *root) {
        if (root==NULL) return 0;
        int max = root->val;
        maxPathSumToNode( root, max );
        return max;
    }
};