124. Binary Tree Maximum Path Sum

/* DFS O(n) */
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root){
        solve(root);
        return maxSum;
    }

    public int solve(TreeNode root){
        if(root==null) return 0;
        int ans=Integer.MIN_VALUE;
        int left =Math.max(0, solve(root.left)); // If the sum is negative, ignore the subtree, -ve values
        int right=Math.max(0, solve(root.right));
        //merging at root, completing path
        maxSum = Math.max(maxSum, root.val + left + right);
        //taking only one subtree for one path and carry it upward
        return root.val + Math.max(left, right);
    }
}

/*
LOGIC---
maximum path sum = root node + max of left subtree + max of right subtree
Now we can have this root node or genral node anywhere on tree
    1
   / \
   2 3
Now (2,1,3), (1,2,3), (3,1,2) is a path.
2 is a path in itself, so does 1 or 3.
1,2 is a path, (2,1), (1,3)
So at node 1 we have two choices, either split to left or right.
If we consider only left or right, we can consider it a part and carry it upward if 1 is a child node.
Now if we do 1+2+3. this is a complete path we cant take more.

This will make clear think,
  5
   \
    1
   / \
   2 3

So possible path sum = (2+1+3) | (2+1+5) | (3+1+5)
1,2,3 => is a complete path in itself becuase we took both left and right subtree => merging at 1
2,1,5 => for 5 we only took one path of left on 1 => 5,1,2 => merging at 5
3,1,5 => for 5 we only took one path of right on 1 => 5,1,3 => merging at 5

So, in fact its a choice of getting max between left and right and deciding a joining node

TC- O(n) => every node is travelled once
SC- O(h) -> height of binary tree
*/