Binary Tree Maximum Path Sum -- LeetCode

[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]
If the path can be only link (i.e. no both left and right nodes of one node allowed to be in the path), the problem is simple. Suppose path with max single-sided path ending at Node N (from bottom to up),
       SingleSidePathMax(N) = max (N.value,
                                                     N.value+ SingleSidePathMax(N.left),
                                                     N.value+ SingleSidePathMax(N.right) );

Going through all nodes in the tree, this will get the max sum of single-sided path.

To consider the path with a node N, whose both left and right are included in the path, it can calculated by,
      PathMax(N) = max ( SingleSidePathMax(N), N.value+SingleSidePathMax(N.left) + SingleSidePathMax(N.right) );

Therefore, apply post-order traversal in the Binary Tree, and calculate the single-sided path max and dual-sided path max of each node, the max path sum of all paths can be found.

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

};