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.

&nbsp;
Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -&gt; 1 -&gt; 3 with a path sum of 2 + 1 + 3 = 6.


Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -&gt; 20 -&gt; 7 with a path sum of 15 + 20 + 7 = 42.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 3 * 104].
	-1000 &lt;= Node.val &lt;= 1000


class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.res=root.val
        def solving(root):
            if not root:
                return 0
            current=root.val
            sleft,sright=float('-inf'),float('-inf')
            if root.left:
                sleft=solving(root.left)
                if(sleft>=0):
                    current+=sleft
            if root.right:
                sright=solving(root.right)
                if(sright>=0):
                    current+=sright
            if(current>self.res):
                self.res=current
            return max(root.val, root.val+sleft, root.val+sright)
        solving(root)
        return self.res
class Solution {

    int[] ans = new int[1];
    public int maxPathSum(TreeNode root) {
        ans[0]=root.val; //Handle edge case
        dfs(root);
        return ans[0];
    }

    public int dfs(TreeNode root){

        if(root==null)
            return 0;

        int left=Math.max(0,dfs(root.left)); //Check on the left subtree and if returned negative take 0
        int right=Math.max(0,dfs(root.right)); //Check on the right subtree and if returned negative take 0

        int maxInTheNode=root.val+left+right; //Calculating the max while including the root its left and right child.
        ans[0]=Math.max(ans[0],maxInTheNode); //Keeping max globally

        return root.val+Math.max(left,right); //Since only one split is allowed returning the one split that returns max value
    }
}
class Solution {
public:
    int rec(TreeNode* root,int& res ){
        if(root==nullptr) return 0;
        // maximum value from left
        int l = rec(root->left,res);
        //maximum value from right
        int r = rec(root->right,res);

        //check if path can go through this node ,if yes upadte the result value
        res = max(res,root->val+l+r);

        // return the maximum non-negative path value
        return max({l+root->val,r+root->val,0});
    }
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        int x = rec(root,res);
        return res;
    }
};
var maxPathSum = function(root) {
    let res = -Infinity;
    function solve(root){
        if(!root){
            return 0;
        }
        
        let left = solve(root.left);
        let right = solve(root.right);
        //ignore the values with negative sum
        let leftVal = Math.max(left, 0);
        let rightVal = Math.max(right,0);
        
        let localMax = leftVal + rightVal + root.val;
        res = Math.max(localMax,res);
        return Math.max(leftVal, rightVal) + root.val;
        
    }
    solve(root);
    return res;
    
};
Binary Tree Maximum Path Sum