Binary Tree Maximum Path Sum

2 min read
LC-Hard
Binary Tree

Oct 21, 2022

3 years ago

LeetCode

Solution

For a path to be considered a path, we can only SPLIT once, i.e. consider both children of the current node ONCE
Use recursive Depth-first Search and go bottom-up to avoid repeated work
The return value at any point would be the max value we can get from that node, given that we're NOT allowed to split
- BUT, remember that we also need to update the answer by considering if we can split from that node.
  - I.e. say your recursive call is at the node 3
    - You already split from 1 to get here, so ONE your split is technically done, which means the return value from 3 would be the max value of the left and right subtrees PLUS the current value. In this case, it would be 5 + 3 = 8.
    - But, we also need to consider the fact that a split can be made from 3, which would mean our path would become 4 + 3 + 5 = 12. This is actually the answer. We don't want to return this value but update the answer with this.
- Do this for all nodes and you'll have your answer
- KEEP IN MIND ALSO that since there are negative numbers, we will benefit from NOT CONSIDERING negative numbers if they reduce our overall sum.
  - Say for a node, our left and right subtrees are both negative numbers- if we consider even one of them, it would bring down our max path sum. So just not consider them
    - To not consider them, use a max(0, val) for both the path sums of left and right subtrees

Time	Space	Explanation
`O(n)`	`O(h)`

def maxPathSum(self, root: Optional[TreeNode]) -> int: ans = root.val # This is important, if there's only one node in tree and that's negative, we need to return the root's value def dfs(root): nonlocal ans if root is None: return 0 # The max functions below take care of the cases where a child node has a negative return value left_max_path_sum = max(0, dfs(root.left)) right_max_path_sum = max(0, dfs(root.right)) ans = max(ans, root.val + left_max_path_sum + right_max_path_sum) return root.val + max(left_max_path_sum, right_max_path_sum) dfs(root) return ans