[Leetcode] Binary Tree Maximum Path Sum

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.


Analysis:
Top down approach as stated from online sources.

Solution:

// return max path sum starts from root
int findMax(struct TreeNode *root, int *max_sum)
{
    if(root == NULL)
       return 0;
       
    int left = findMax(root->left, max_sum);  
    int right = findMax(root->right, max_sum);
    
     // compare max_sum with current path sum root->val + left + right
    *max_sum = *max_sum > (root->val + left + right) ? *max_sum : root->val + left + right;
    
    // notice we only pick either left or right subtree
    int max_sub = left > right ? left : right;
    
    int max_root_sub = root->val + max_sub;
    
    // if root->val + max_sub is less than 0, we shouldn't add it to root's parent as it reduces            sum of the path, return 0 instead
    return max_root_sub > 0 ? max_root_sub : 0;
}

int maxPathSum(struct TreeNode *root) {
    
    int max_sum = INT_MIN;
    
    findMax(root, &max_sum);
    
    return max_sum;
    

}