Question: https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
Question Name: Binary Tree Maximum Path Sum
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a tuple def maxPathSumHelper(self, root): maxPathSumInThisSubTree = root.val maxPathSumToUpper = root.val # The maximum path sum, which could # be used by its ancestors. left, right = None, None if root.left != None: left = self.maxPathSumHelper(root.left) # Any path, who has both the nodes of root's son(s) AND root's # ancestors, must have the node "root" of this subtree. maxPathSumToUpper = max(maxPathSumToUpper, root.val + left[1]) # The maximum path of current subtree may not cross its root. maxPathSumInThisSubTree = max(maxPathSumInThisSubTree, maxPathSumToUpper, left[0] ) if root.right != None: # Same as the left son. right = self.maxPathSumHelper(root.right) maxPathSumToUpper = max(maxPathSumToUpper, root.val + right[1]) maxPathSumInThisSubTree = max(maxPathSumInThisSubTree, maxPathSumToUpper, right[0] ) # If both the left son and right son exist, the maximum path of this # subtree may across the left subtree, current root and the right # substree. if left != None and right != None: maxPathSumInThisSubTree = max(maxPathSumInThisSubTree, root.val + left[1] + right[1] ) return maxPathSumInThisSubTree, maxPathSumToUpper # @param root, a tree node # @return an integer def maxPathSum(self, root): return self.maxPathSumHelper(root)[0] |