binary tree maximum path sum with 2 returns

Question

I am trying to find the maximum path sum of a binary tree, which is question 124 on Leetcode. Can someone help me on what does the "return max(left, right, root.val)" do? Where is it used in the "maxPathSum" or "diameterHelper" function? Thank you so much!!

[1]: https://i.stack.imgur.com/liGMD.png

class Solution:
    def maxPathSum(self, root):
        max_so_far = [root.val]

        def diameterHelper(root, max_so_far):

            if root.left == None and root.right == None:
                print(root.val)
                #print(max_so_far)
                if root.val > max_so_far[0]:
                    max_so_far[0] = root.val
            #    print("222222")
                return root.val

            left, right = root.val, root.val

            if root.left is not None:
                left = root.val + diameterHelper(root.left, max_so_far)
                #print(left)

            if root.right is not None:
                right = root.val + diameterHelper(root.right, max_so_far)
            #print(max_so_far)
            #print(root.val)
            cur_max = left + right - root.val
            if cur_max > max_so_far[0]:
                max_so_far[0] = cur_max
            if root.val > max_so_far[0]:
                max_so_far[0] = root.val
            if left > max_so_far[0]:
                max_so_far[0] = left
            if right > max_so_far[0]:
                max_so_far[0] = right
            #print(1)
            #print(max_so_far[0])
            return max(left, right, root.val)

        diameterHelper(root, max_so_far)
        return max_so_far[0]

Rory Daulton Rory Daulton · Accepted Answer · 2018-11-26T01:44:57

The function diameterHelper returns the maximum sum of paths that begin at the current node (called root unfortunately) and go down the binary tree. It also updates the value of the max_so_far variable, but that is irrelevant to your questions.

At one point, the variable left is set to the maximum sum of paths that begin at the current node and go down the binary tree through the left child of the current node. Similarly, the variable right is set to the maximum sum of paths that begin at the current node and go down the binary tree through the right child of the current node.

At the end of function ``, your line return max(left, right, root.val) is executed. That means the maximum sum of paths down from the current node has three possibilities. It could be a path through the left child, or it could be a path through the right child. One more possibility is that the max path goes through neither child, which means it is simply the simplest path of just the one node, the current one. This happens when there are no children nodes or when all paths down either child have negative sums.

So the line examines all three possibilities, chooses the largest path sum from these, and returns that value to the calling function. So the function does indeed return the maximum sum of paths down from the current node.

At some point, the highest-level node in the maximum-sum path will be examined. Then both max path lengths down from that node will be used and summed to get the max-sum path length in the subtree. This differs from the previous maxes in that this path does not necessarily go down from the current node--it just goes through the current node.

binary tree maximum path sum with 2 returns

1 Answers