[LeetCode] Binary Tree Maximum Path Sum

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:
Note: the maximum path doesn't have to include the root. So, if we do DFS, we need to record the maximum path sum of a sub tree. For root->left, the DFS function should return the maximum path sum that ends at root->left, in order to connect to root. root->right should be the same.

class Solution {
public:
    int maxPathSum(int & maxSum, TreeNode* root) 
    {
        if(!root) return 0;
        int tmp = root->val;
        int left = maxPathSum(maxSum, root->left);
        if(left>0) tmp+=left;
        int right = maxPathSum(maxSum, root->right);
        if(right>0) tmp+=right;
        //Note: maxSum has already been compared with left and right
        //      in recursive calls
        maxSum = max(tmp, maxSum);
        return max(root->val, max(left, right) + root->val);
    }
    int maxPathSum(TreeNode* root) {
        if(!root) return 0;
        int maxSum = INT_MIN;
        int res = maxPathSum(maxSum, root);
        return max(res, maxSum);
    }
};