# Question

Formatted question description: https://leetcode.ca/all/124.html

124	Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

1
/ \
2   3

-1
/  \
2   -3

1
/  \
-2   -3

@tag-tree



# Algorithm

In the recursive function, if the current node does not exist, it directly returns 0.

Otherwise, call the recursive function on its left and right child nodes respectively. Since the path sum may be negative, and it is not supposed to add a negative path sum, so compared with 0, choose the larger one and add a positive number.

Then to update the global maximum result res, which is the sum of the maximum path ending at the left child node plus the sum of the maximum path ending at the right child node, plus the current node value, which is a complete path.

The return value is the larger value of left and right plus the value of the current node. Because the return value is defined as the sum of the path ending at the current node, only the larger value of left or right can be used. Not both.

The key is to judge well, the maximum value is 4 situations in total

1. left + root + right
2. left + root
3. right + root
4. root

It is to judge which is negative, if left and right child is negative, then discard it to 0 Compare with max

• left+right+root,
• Still root,
• Or root+left,
• Or root+right

The final return is

• Look at root,
• Or root+left,
• Or root+right

Note that the max comparison is to add up both left and right, but when returning, it can only be either the left or the right

# Code

Java

• 
public class Binary_Tree_Maximum_Path_Sum {

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class Solution {
int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {

// the path does not have to include root, but this max path sub-tree must have a sub-root
// eg: [1,-2,-3,1,3,-2,null,-1]

if (root == null) {
return 0;
}

traverse(root);

return max;
}

private int traverse(TreeNode root) {

if (root == null) {
return 0;
}

/*
1. root itself only
2. root + left-child
3. root + right-child
4. root + left-child + right-child
*/

int leftChild = traverse(root.left);
int rightChild = traverse(root.right);

int localMax = Math.max(Math.max(root.val, root.val + leftChild), Math.max(root.val + rightChild, root.val + leftChild + rightChild));

// System.out.println("root: " + root.val + ", localMax: " + localMax);

max = Math.max(max, localMax);

return Math.max(root.val, Math.max(root.val + rightChild, root.val + leftChild));
}

}

}

• // OJ: https://leetcode.com/problems/binary-tree-maximum-path-sum/
// Time: O(N)
// Space: O(H)
class Solution {
int ans = INT_MIN;
int dfs(TreeNode *root) {
if (!root) return 0;
int left = dfs(root->left), right = dfs(root->right);
ans = max(ans, root->val + left + right);
return max(0, root->val + max(left, right));
}
public:
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""

def dfs(root):
if not root: return (0, float("-inf"))
(l, lm), (r, rm) = map(dfs, [root.left, root.right])
return (max(root.val, root.val + max(l, r)), max(lm, rm, root.val + max(l, r), root.val, root.val + l + r))

return dfs(root)