Leetcode 124: Binary tree maximum path sum - a quick review

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

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.

Walk through the above example in the diagram and have some more discussion: 

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.

Blogs about leetcode 124: 

Previous blogs about Leetcode 124: 
1. blog 1:
http://juliachencoding.blogspot.ca/2015/07/leetcode-maximum-binary-tree-path-sum.html

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

3.
Practice on May 31, 2016, first version:

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

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

4. blog 4: 

http://juliachencoding.blogspot.ca/2016/05/leetcode-124-binary-tree-maximum-path.html

I like the encouraging verse. https://t.co/7wUhmyPoDx

— jianmin chen (@jianminchen) June 5, 2016