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
        return ans

Problem solution in Java.

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

Problem solution in C++.

class Solution {
    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; 
    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;