Leetcode 124: Binary Tree Maximum Path Sum - reasoning and analysis (I, II, III)

May 31, 2016

Review the blog:
http://juliachencoding.blogspot.ca/2015/07/leetcode-maximum-binary-tree-path-sum.html

http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

Practice on May 31, 2016, first version:

https://gist.github.com/jianminchen/432bdb1af38a1ec6f4a0741420891ebf

Second version: add more comment:
https://gist.github.com/jianminchen/578656e1079e8c58b08dd19f5b027e68

The above second version line 133 - line 137 can be simplified as one statement:
int value = root.val + ((left>0)?left:0) + ((right>0)?right:0);

Third version: line 133 - line 137 -> one line
https://gist.github.com/jianminchen/9fc060ae74290637f732a0fcaf820f44

Reasoning and analysis (I):

Write some reasoning and analysis.

Let us talk about an example first:
In the practice on May 31, 2016, line 60 - 79, test case 3:
https://gist.github.com/jianminchen/578656e1079e8c58b08dd19f5b027e68

The maximum path sum in the above tree is highlighted using red color, node 6->9->-3->2->2. Any two nodes in the tree can form a unique path, and the choice of path is N^2, N is the total nodes in the tree.

If we do not use recursive solution, try to use brute force solution:
1. Find any two nodes in the tree, and then find the path, and calculate the sum of path.
(June 24, 2016 but least common ancestor is much more difficult problem to solve!)
For example, maximu path, we have to find the common ancestor of those two nodes with value 6 (root->left) and node with value 2 (root->right->right->left) first, and then, the path can be formed.

So, the recursive solution can be based on the following facts:
1.  Any node in the tree can be visited from top to down, preorder traversal, once. And the node is treated as root node of one subtree.

2. So, just consider the maximum path starting from root node, this way, the recursive function can be set up.
2.  Any two nodes in the tree  ->  the root to any node in the tree (simplify the case)
3.  the maximum path in the above diagram: 6->9->-3->2->2 -> construct by the root to any node in the tree.

 value1:  Root node with value 9,
 value2:  Root-> left node's maximum value of "the root to any node in the tree"
 value3:  Root-> right node's maximum value of "the root to any node in the tree"

 the maximum path = value1 +(value2>0?value2:0) + (value3>0?value3:0)

So, the recursive solution can be formed quickly.

August 4, 2016
Come back to review the previous work, but it is still not easy to tell the ideas to solve the problem.

Reasoning and analysis (II):
Add one more explanation to walk through the example:
First talk about "maximum value cross root" - variable: maxValueCrossRoot,
each node is the root of its subtree, so the maximum one will be maximum one from the following list:

1. n1: root node (9): need to calculate maximumEndByRoot on right child (-3) first.
2. n2: left child (6):
3. n3: right child (-3):
4. n4: right->right child(-6): -6
5. n5: right->right->right (2): 4
6. n6: right->rigth->right->left(2) : 2
7: n7: right->right->right->left->left(-6): -6
8: n8: right->rigth->right->left->right(-6): -6

It is comparison by values.
Tip: 1.The idea to get the maximum value is to pass a reference int to any recursive function. Any subtree will have one value, and compare with the global variable's value.
2. Use preorder traversal to travel tree once.

And "maximum value end by root" - variable: maximumEndByRoot

the above node n8: -6
n7: -6
n6: 2
n5: 4
n3: +1
n2: 6

So, the root node maxValueCrossRoot = 9 + 6 + 1 = 16
maximumByEnd = 15.

Tip: 1. use recursive function with return value - maxValueEndByRoot, the formula is easy to recall.
2. use preorder traversal to travel tree once.

The above case is coincident, the maxValueCrossRoot is ended at the root node n1 (value 9), which may be anywhere (ni, i is one value from 1 to 8) in the tree.

Reasoning and analysis (III):
Creative way to solve the problem:

1. Work on a simple problem first:
Maximum value end by root in a binary tree - in other words, maximum value from the root node to any node in binary tree

https://gist.github.com/jianminchen/8f3ec942e90bcdca5a1569d1a70e92df

Goal: be able to write the function in 10 minutes, verify code with static analysis.

2. Add one more function in the above program -
Based on the simple problem - maximum value end by the root node, add one more task to the function:
maxValueCrossRoot calculation. (bottom up solution)
https://gist.github.com/jianminchen/5eab22189f0fd7a58aa4fbc56b725dd8

Add 2 more lines of code: line 104, 105, add one more input argument - ref int maxCrossRoot, 3 places update

Goal: make it 10 minutes to add

So, overall, it should be less than 20 minutes code writing. Follow the function - do one task only. a time.

1. Step 1: write a simple recursive function - preorder traversal. Pay attention to negative value node, just ignore them if it is. Avoid if statement, just get minimum value through 3 values, make it one line statement - no if/else discussion of left/right child value > 0.

Only 5 lines of code. Short and concise.

2. Step 2: add 2 lines code (line 104, line 105), 3 changes - add one more argument (line 96, line 101, line 102):