LeetCode: Binary Tree Maximum Path Sum

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.

这个题让我做的有点儿恶心了

算法本身不难，瞬间找到solution: DFS recursion，题目要求有些变态， the value of a node can be positive, 0 and negative. 

Key points:

•  Use a member variable maxSum. If c++, can use " int maxPathSumRe(TreeNode *root, int &max)"
•  return value should be Maximum(left, right) + curVal

 Code