Binary Tree Maximum Path Sum

Another trees related problem :)

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

I think these tree related problems are quite easier compared to other data structures.

Tree traversals are only BFS or DFS (pre-order, in-order and post-order). If we know what traversal to follow, problem is solved.

For this problem, we should follow post-order traversal as we need subtrees paths.

Write a recursive post order function, which does calculating of the path sum and updating max path sum then return the max path sum.
path sum of node = node value + left subtree gain
+ right subtree gain
gain of node = its node value [+ max(left/right subtree not both)]

Below is the solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/* Its a post order function,
   calculating the pathsum and updating max val
   then return the max pathsum
   path sum includes node values + left subtree path sum
   + right subtree path sum
   while return the gain, gain can include
   its node value [+ max(left/right subtree not both)]
   */
int max_gain(struct TreeNode* nd, int *mg){
    if (!nd)
        return 0;
    int lg, rg;
    lg = max_gain(nd->left, mg);
    rg = max_gain(nd->right, mg);
    lg = (lg < 0) ? 0 : lg;
    rg = (rg < 0) ? 0 : rg;
    if ((*mg) < (nd->val+lg+rg))
        (*mg) = nd->val+lg+rg;
    
    if (lg > rg) rg = lg;
    return(nd->val+ rg);
}


int maxPathSum(struct TreeNode* root){
    int g=0, mg=0;
    if (!root) return 0;
    mg = root->val;
    g = max_gain(root, &mg);
    return mg;
}