Problem
This is a leetcode.com problem.
For this problem, a path is defined as any sequence of nodes from some
starting node to any node in the tree along the parentchild
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.
Following is my solution that is accepted.

As you can see I have used a magic number in place of inf. This is not only inelegant, it will actually produce wrong answer if the input node has values in that range. I can think of a few ways to solve it, but I am open to suggestions about how you would do it. I can perhaps use special value like None but that introduces extra if logic that’s not that beautiful. Are there better ideas?

Do you have suggestions for better names for variables and methods? Please ignore the name of class (and the fact that it does use class) since this is due to how Leetcode’s wants it to be written.
To better understand the code, the intuition is, for any given subtree rooted at node n, I calculate the maximum path that includes n as one endpoint and ends within that subtree. I also calculate the maximum path that is between any two node in that subtree (to do that I take the max of few things). The global solution is then computed at the root of the whole tree.
# 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
"""
_, max_path = self.max_path(root)
return max_path
def max_path(self, node):
if node == None:
return 0, 9999999
max_path_from_left, max_path_in_left = self.max_path(node.left)
max_path_from_right, max_path_in_right = self.max_path(node.right)
max_path_from_current = max(
max_path_from_left + node.val,
node.val,
max_path_from_right + node.val)
max_path = max(max_path_in_left, max_path_in_right,
max_path_from_left + node.val + max_path_from_right,
max_path_from_current)
return max_path_from_current, max_path
Solution

If you want −∞$\infty $, just write
float('inf')
. 
The names could be improved by removing the common prefix
max_path_
, usingto
instead offrom
, andnode
instead ofcurrent
. (The replacements are shorter than the originals, so reduce the size of the code without reducing readability.) 
The computation of
max_path_from_current
(which becomesto_node
after my renaming), can be simplified by pulling the addition ofnode.val
out of the call tomax
:to_node = node.val + max(0, to_left, to_right)

Since
max_path
is only called frommaxPathSum
it makes sense for it to be a local function there. Then you could avoid the unnecessary use ofself
.
Revised code:
def maxPathSum(self, root):
def max_path(node):
if node is None:
return 0, float('inf')
to_left, in_left = max_path(node.left)
to_right, in_right = max_path(node.right)
to_node = node.val + max(0, to_left, to_right)
in_node = max(in_left, in_right, to_left + node.val + to_right, to_node)
return to_node, in_node
return max_path(root)[1]