Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.
Max Path Sum = 6
The following algorithm uses recursion to find vertical maximum path sum, which is the maximum path sum from a node down to its descendant. Then the vertical path sum is used to find cross maximum path sum, which is from child to child.