Friday, August 23, 2019

Leetcode solution 124: Binary Tree Maximum Path Sum

Problem Statement 

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]

      / \
     2   3

Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]

   / \
  9  20
    /  \
   15   7

Output: 42
Problem link


Video Tutorial

You can find the detailed video tutorial here

Thought Process

When dealing with binary tree related problem, traversals using recursion is our friend. It seems we can perform a post-order traversal, and keep track of the maximum sums.

If the path cannot go across root, then in each post-order step, we will have the max_sum_of_the_left_path, max_sum_of_the_right_path, the current_node_value, we simply return and record

single_path_max = max(the current_node_value, max(max_sum_of_the_left_path, max_sum_of_the_right_path) + current_node_value)

However, the problem allows a path that goes through the root, therefore, we need to also record a max between left + current node value + right, i.e.,

global_max = max(single_path_max, max_sum_of_the_left_path + current_node_value + max_sum_of_the_right_path)

One caveat is in your recursion, we should still return the single_path_max. The reason we should not return the global_max is in that case, it will not be a single node to single node path.


Post-order recursion

Time Complexity: O(N), each node is visited once
Space Complexity:No extra space is needed other than the recursion function stack


No comments:

Post a Comment