[Leetcode] Binary Tree Maximum Path Sum

Problem

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Algorithm

Use a helper class PathSum with two fields to store the intermediate result. The startRoot stores the path sum start with root, and the crossRoot stores the path sum cross the root. Since the left subtree may have negative start wit root path sum, we need to compare it with zero when compute the max path sum start with root. 

Code