# 124. Binary Tree Maximum Path Sum (any node to any node)

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 must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

``````       1
/ \
2   3
``````

Return`6`.

Thoughts:

in top down order, for each node do:

1. calculate the current path sum, update the record
2. pass the larger branched sum value to the parent

Code:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
maxPathSumDown(root);
}

int maxPathSumDown(TreeNode * cur){
if(!cur) return 0;

int left = max(0, maxPathSumDown(cur->left));
int right = max(0, maxPathSumDown(cur->right));
return max(left, right) + cur->val;
}
};
``````

Code without global variable

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
maxPathSumDown(root);
}

int maxPathSumDown(TreeNode * cur){
if(!cur) return 0;

int left = max(0, maxPathSumDown(cur->left));
int right = max(0, maxPathSumDown(cur->right));
return max(left, right) + cur->val;
}
};
``````

Code (Python)

``````# 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):
maxVal = float("-inf")
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.maxPathDown(root)
return self.maxVal

def maxPathDown(self, cur):
if not cur:
return 0
left = max(0, self.maxPathDown(cur.left))
right = max(0, self.maxPathDown(cur.right))
self.maxVal = max(self.maxVal, left + right + cur.val)
return max(left, right) + cur.val
``````

Special Thanks to wei-bung for providing this solution