Maximum Sum Path in a Binary Tree

Question

I am trying to solve this question: https://leetcode.com/problems/binary-tree-maximum-path-sum/description/.

To find maximum sum path is like finding maximum path between any two nodes, that path may or may not pass through the root; except that with max sum path we want to track sum instead of path length.

So, I adapted the diameter of a binary tree's solution to find the maximum sum path.

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

class Solution:

    def height(self, root):
        if root==None:
            return 0

        lh = self.height(root.left)
        rh = self.height(root.right)

        return max(root.val+lh, root.val+rh)

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root==None:
            return 0

        lh = self.height(root.left)
        rh = self.height(root.right)

        ld =  self.maxPathSum(root.left)
        rd =  self.maxPathSum(root.right)

        return max(lh+rh+root.val, root.val+ max(ld , rd))

My solution is passing 40 test cases before failing.

I am stuck at trying to figure out the correct solution. My solution works for finding the diameter, I just added sum in the return values.

Why is this not a generic solution as i am clearly traversing all the paths and taking appropriate max in return values.

Thanks for your help.

user3386109 user3386109 · Accepted Answer · 2018-03-02T08:59:57

The problem is this line

return max(lh+rh+root.val, root.val+ max(ld , rd))

It should be

return max(lh+rh+root.val, max(ld , rd))

Note that the root node is not part of the path for ld and rd.

Maximum Sum Path in a Binary Tree

1 Answers