### 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]1/ \23Output:6

**Example 2:**

Problem linkInput:[-10,9,20,null,null,15,7] -10 / \ 920/ \15 7Output:42

### 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.

### Solutions

#### 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

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!