1
\$\begingroup\$

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

Given a non-empty binary tree, find the maximum path sum.

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.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Inputs

[1,2,3]
[-10,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7999999,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7]

Outputs

6
42
66
791
8001552

Code

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

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def depth_first_search(node: TreeNode) -> int:
            if not node:
                return 0
            left_sum = depth_first_search(node.left)
            right_sum = depth_first_search(node.right)
            if not left_sum or left_sum < 0:
                left_sum = 0
            if not right_sum or right_sum < 0:
                right_sum = 0
            self.sum = max(self.sum, left_sum + right_sum + node.val)
            return max(left_sum, right_sum) + node.val

        self.sum = float('-inf')
        depth_first_search(root)
        return self.sum

References

\$\endgroup\$
1
\$\begingroup\$

Unnecessary checks in depth_first_search()

The function depth_first_search() always returns an integer value, never None. So the check for a partial sum being None or < 0 can be rewritten using max():

left_sum = max(0, depth_first_search(node.left))
right_sum = max(0, depth_first_search(node.right))
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.