学步园

解题的关键在于这条路径只能是先往上走，到达某个最高点，再往下走，换句话说，只能有一次转折的机会。所以递归这棵树，记录以某个子节点为转折点时的最大值。值得注意的是树节点的值有负值，所以如果某个子路径的和小于0，放弃它（设置和为0）。

class Solution {
public:
	int maxPathSum(TreeNode *root) {

		int maxSum = -1 << 30;

		int leftMax = pathMaxSum(root->left, maxSum);
		if (leftMax < 0)
			leftMax = 0;
		int rightMax = pathMaxSum(root->right, maxSum);
		if (rightMax < 0)
			rightMax = 0;

		int pathSum = leftMax + rightMax + root->val;
		if (pathSum > maxSum)
			return pathSum;
		else
			return maxSum;
	}


	int pathMaxSum(TreeNode* node, int& maxSum)
	{
		if (node == NULL)
			return 0;

		int leftMax = pathMaxSum(node->left, maxSum);
		if (leftMax < 0)
			leftMax = 0;

		int rightMax = pathMaxSum(node->right, maxSum);
		if (rightMax < 0)
			rightMax = 0;

		if (leftMax + rightMax + node->val > maxSum)//turn down at this point
			maxSum = leftMax + rightMax + node->val;

		int pathMax = leftMax > rightMax ? leftMax : rightMax;
		pathMax += node->val;

		return pathMax;
	}
};