LeetCode problem #124. Binary tree Maximum path sum.

Problem Statement:

    Given a tree, task is to find out the path with maximum sum of the elements along the path. 

The path can be anywhere in the tree and need not go along the root and the nodes shouldn't be skipped in the path.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

 Approach to the solution:  

• Approach here is simple, first traverse the tree in post order manner.
• Keep track of maximum values of left and right.
• Keep track of maximum values of left side and right side.
• Compare and keep track of maximum values between maximum side max and sub tree.
• Keep track of global maximum sum of the path in one variable
• Compare global maximum sum with the sum which got from the above process.
• Return that maximum sum.
• This maximum sum is the maximum path of the sum with the given conditions.

 Solution in C++:

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ret = INT_MIN;
        cal(root, ret);
        return ret;
    }
   
    int cal(TreeNode* root, int &ret){
        if(!root)
            return 0;
        int left = cal(root->left, ret);
        int right = cal(root->right, ret);
        int maxlr = max(left, right);       
        int side_max = max(maxlr + root->val, root->val);       
        int subr_tree_max = max(side_max, left + right + root->val);       
        ret = max(ret, subr_tree_max);       
        return side_max;
    }
};