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 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.
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