\$\begingroup\$\$\endgroup\$
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 3Output: 6Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7Output: 42Inputs
[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
642667918001552Code
# 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 = rightclass 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.sumReferences
1 Answer1
\$\begingroup\$Unnecessary checks in
\$\endgroup\$
0Unnecessary checks indepth_first_search()
The functiondepth_first_search() always returns an integer value, neverNone. So the check for a partial sum beingNone or< 0 can be rewritten usingmax():
left_sum = max(0, depth_first_search(node.left))right_sum = max(0, depth_first_search(node.right))
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.