Leetcode 124: Binary Tree Maximum Path Sum - Single Responsibility Principle (SRP)

August 4, 2016

 If you do not have idea how to solve the Leetcode 124, please read the blog first, warm up with ideas to solve the problem:
http://juliachencoding.blogspot.ca/2016/08/leetcode-124-binary-tree-maximum-path.html

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.

Creative way to solve the algorithm problem:

Review S.O.L.I.D. principles, one of principle - Single Responsibility Principle. 

Use SRP to write the function, one task a time. 

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.

1. Step 1: write a simple recursive function - preorder traversal. 
A: Pay attention to negative value node. 
(if both left and right child node's value are negative value, maximum value path ending at root node is root node's value itself; value >= root node's value) -> come out formula: line 98, maximum value of 3 values. 
  
B: 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. Add one more task in the above function -

Usually the function should be designed to work on one task only. Need to add a second task to the function. 

Based on the simple problem - maximum value end by the root node, add one more task to the function:
maxValueCrossRoot calculation. (bottom up solution)

Try to calculate the maximum path sum cross the root node in the tree. 

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: complete the code change in 10 minutes. 

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

So, overall, less than 20 minutes code writing. Follow the above 2 steps - write a function to complete the first task, and then, add second task to the function. 

Questions and Answers:

1. How to make this algorithm an easy one? 
A few people complain that the algorithm is too tough to work on through their blogs. Julia also spent hours to work on it in 2015, and then, Feb. 2016. 

In August 2016, Julia spent hours to review the algorithm, wrote 2 blogs.  

For easy to write, try SRP techniques, work on maximum path end by root first, then piggyback the max path cross the root. It will help to ease the stress. 


I learned to stay and work hard every day to get the chance to be the best. - Karolina Pliskova
Julia, can you repeat the sentence word by word?

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

— jianmin chen (@jianminchen) June 5, 2016