Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Examples

     1
    / \
   2   3
Input: [1,2,3]   -> 6   (path: 2->1->3)

      -10
      /  \
     9   20
        /  \
       15    7
Input: [-10,9,20,null,null,15,7]  -> 42  (path: 15->20->7)