124. Binary Tree Maximum Path

This is the Leetcode question called "Binary Tree Maximum Path):

https://leetcode.com/problems/binary-tree-maximum-path-sum/

Every nodes have a specific value. Some are positive and some are negative.

We can start from any node of tree.

When we start, we can make a direction to other node. 

Solution:

First, we make the list name "res" to return the sum. 

The function "dfs" is used for recurssion and return the value of the maximum case when we go thorugh the right side or left side.

While doing recurssion, we compute the value of the path to find out which is the maximum path.

This is the code for computation.

After the recurssion, res[0] is the value of maximum path. 

 

In example 1, we can start 2 or 1. 

2 start: we can move to 1, and then 3. So, the sum is 2 + 1 + 3 = 6.

 

1 start : we can move to 2 or 3. The sum of the path will be 1 + 2 = 3 or 1 + 3 = 4. 

However, we can not return to 1 and move to 2!! The path has only one direction in this algortitms. 

ex ) 1 -> 3 -> 1 -> 2 ==> 1 + 3 + 1 + 2 = 7 (X)

 

 In example 2, this is a little bit different. 

We can see the most top parent's node is "-10."

We don't need to include that node to our path. Because, even 9 - 10 = -1 (negative). 

The maximum value of sum is 15 --> 20 --> 7 ==> 15 + 20 + 7 = 42.