124. Binary Tree Maximum Path Sum

-
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
      / \
     2   3

Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42
---
Intuition

 Consider binary tree with 3 nodes => 1 root + 2 children

There are four ways to compute path sum
  1. Node alone i.e., no children
  2. Node + left child
  3. Node + right child
  4. Node + left child + right child (*)
The answer for this tree is max of the above 4 sums

2, 3 are essentially root + max child
The choices reduce to
  1. Node alone i.e., no children
  2. Node + max(left child, right child)
  3. Node + left child + right child (*)
1 above is right choice if left child, and right child contribute negative values to the total
We can eliminate -ve value with a simple comparison against 0 => Math.max(-ve, 0)

The choices reduce to
  1. Node + max( max(left child, 0), max(right child, 0))
  2. Node + left child + right child (*)
The first path means path from root + 1 child
Second path means path inclusive of root + 2 children

Answer for 3 node tree is the max from above two paths

(*) Path inclusive of root and both children deserves some attention

Consider this tree is subtree under another root, if we've already chosen the path inclusive of root in the subtree (*), then this path cannot go through the root again.
So this path can only contribute to the final answer if this is the largest path sum in the whole tree

So for root, there are 2 choices again
  1. Do not include path going through self => Take max from
    1. Global max from left child
    2. Global max from right child
  2. Include path going through self = > Add
    1. Self
    2. One sided path from Left child
    3. One sided path from Right child
Final answer is max from above two paths i.e., global max
---
Time - O(n)
Space - O(n) - recursion stack
---
Related problems
543-diameter-of-binary-tree
---
Using class variable
---
Without class variable ----