[LeetCode] Binary Tree Maximum Path Sum

Problem Statement (link):

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:
The idea is to use recursive DFS. For each node, we find the max sum for its left and right sub-tree, adding the node's value, we return a max summation to its parent.

In the following code, the maxSum variable is used to record the maximum summation that we got so far. The maxPath variable is the maximum summation of current node value adding its max left and right sub-tree path values.

Code:

/**
 * 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 maxPathSum(TreeNode* root) {
        int maxSum = (root==NULL) ? 0:root->val;
        pathSum(root, maxSum);
        return maxSum;
    }

    // maxSum tracks the current max sum via a particular root node
    int pathSum(TreeNode* node, int& maxSum) {
        if (node==NULL) return 0;

        int l = pathSum(node->left, maxSum);
        int r = pathSum(node->right, maxSum);

        int maxPath = max(l>0?l:0, r>0?r:0) + node->val;
        maxSum = max(maxSum, (l>0?l:0) + (r>0?r:0) + node->val);
        return maxPath;
    }
};