Leetcode Binary Tree Maximum Path Sum problem solution

YASH PAL,

In this Leetcode Binary Tree Maximum Path Sum problem solution, 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 path.

Leetcode Binary Tree Maximum Path Sum problem solution

Problem solution in Python.

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        
        def rec(node):
            nonlocal ans
            if not node:
                return 0

            left = rec(node.left)
            right = rec(node.right)

            ans = max(ans, max(node.val, max(left, right) + node.val, left + right + node.val))
            return max(node.val, left + node.val, right + node.val)

        ans = -1001
        rec(root)
        return ans

Problem solution in Java.

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    public int helper(TreeNode root){
        if(root==null) return 0;
        max=Math.max(root.val,max);
        int l = helper(root.left);
        int r = helper(root.right);
        max=Math.max(max,l+root.val);
        max=Math.max(max,r+root.val);
        max=Math.max(root.val+l+r,max);
        return Math.max(Math.max(l,r)+root.val,0);
    }
}

Problem solution in C++.

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        
        int sum = f(root, res);
        return res;
    }
    
    int f(TreeNode *root, int &res) {
        if(root == NULL)
            return 0;
        
        int r = f(root->right, res);
        int l = f(root->left, res);
            
        int max_sum = max(root->val, max(root->val+l+r, max(root->val+r, root->val+l)));
        res = max(res, max_sum);
        
        return max(root->val, max(root->val+r, root->val+l));
    }
    
};

Problem solution in C.

int res;
int findMax(struct TreeNode*);
int max(int,int);
int max(int x,int y)
{
    return x>y?x:y;
}
int maxPathSum(struct TreeNode* root)
{
     res = INT_MIN; 
    findMax(root);
    return res;  
}

int findMax(struct TreeNode* node)
{   
    if (node == NULL)
    {
        return 0;
    } 
    int left = findMax(node->left);
    int right = findMax(node->right);
    int nodeMax = max(max(node->val, node->val + left + right), max(node->val + left, node->val + right));    
	res=res > nodeMax?res:nodeMax;     
    int temp = max(node->val, max(node->val + left, node->val + right));  
    return temp;
}

coding problems solutions