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.

Method:

Use a recursive method which traverse the binary tree. it also returns the max possible sum of left branch and right branch separately. For example, for node A, when it's left and right node recursive call returned, we will know the max possible sum of left branch, right branch.

Compare the sequence sum and record the max history. For node A, check whether left branch + this node + right branch is the maximum, check whether left branch + this node is max， check whether right branch + this node is max.

When recursive method return, we should only return the max sum of one path - either the left branch + this node, or the right branch + this node. So that this is still a single path and can be used to link by node A's parent node.

class Solution {
public:
    int maxPathSum(TreeNode *root) {
       maxSum = INT_MIN;
       dfs(root);
       return maxSum;
    }
   
private:
    int maxSum;
    int dfs(TreeNode *root){
        if (root==NULL) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
       
        int sum = root->val;
        if (l>0) sum+=l;
        if (r>0) sum+=r;
       
        maxSum = max(maxSum,sum);
        return max(l,r)>0?max(l,r)+root->val:root->val;
    }
};