思路分析
不要被问题表面上的复杂性所吓到，其实它并没有那么困难。首先我们必须弄明白，什么是Path Sum？这里的Path是如何定义的？在这个问题里，我们考虑无向二叉树，因此Maximum Path Sum只存在两种情况：一种是包含根节点的路径，它的一端可能在左子树中，另一端可能在右子树中，也可能只有根节点；另一种子问题则是，Path完全存在于某个子树中。
这样的话，其实问题就和“树的直径”很相似了，依然是利用树的递归性质来求解，也可以看作是树状DP。定义DFS函数为：求从指定根节点出发，值最大的路径。此时我们只需要分析每一层递归中发生的状态转移，总共有三种状态：根节点、根节点与左子树中的最大值路径、与右子树中的最大值路径，取其中最大值即可。
但是注意，上述递归过程的返回值是，从当前根节点出发的最大值路径。但是由于路径两端可以任意，因此DFS的过程中，在每个根节点处计算出的最大值也要被记录，因为任何一个根节点都有可能是最大值路径所通过的那个转折点。
代码
class Solution {
public:
int maxPathSum(TreeNode *root) {
int ans = INT_MIN;
DFS(root, ans);
return ans;
}
int DFS( TreeNode *root, int & ans ) {
if ( root == NULL ) return 0;
int left = DFS(root->left, ans);
int right = DFS(root->right, ans);
int cur_max = root->val;
if ( left > 0 ) cur_max += left;
if ( right > 0 ) cur_max += right;
ans = max(ans, cur_max);
return max(root->val, max(root->val + left, root->val + right));
}
};