学步园

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.

 之前觉得这个是难得一塌糊涂的题目，为五星级难度。

但是自从熟悉了递归回溯，树的遍历，二分法这些相关的算法之后，重新思考一下这道题目。

觉得难度也不过如此，重新评为3到4星级吧。

关键点：

1 每个节点的左右子树都必须保留可以连接的值，本程序作为返回值保留，如节点是root, 可以连接的值为root->val, root->val+left_sum, 或者root->val+right_sum;三个值中的最大值。其中left_sum和right_sum分别为左右子树的最大可连接值。

2 额外使用一个全局变量res保留查找到的最大值，遍历完毕这个res就为结果最终最大值。

说的有点绕口，简单来说就是：

注意区分和保存最终最大值和最大可连接值。

//2014-2-17 update
	int maxPathSum(TreeNode *root) 
	{
		int res = INT_MIN;
		pathSum(root, res);
		return res;
	}
	int pathSum(TreeNode *r, int &res)
	{
		if (!r) return INT_MIN;

		int lsum = pathSum(r->left, res);
		int sum = lsum>0? lsum+r->val:r->val;

		int rsum = pathSum(r->right, res);
		if (rsum > 0) sum += rsum;
		
		res = max(res, max(sum, max(lsum, rsum)));

		int t = max(lsum, rsum);
		if (t > 0) return r->val+t;
		return r->val;
	}

顺便说一句，leetcode上的程序和大多博客的程序都有一个bug，就是当空树的时候返回为0，其实应该返回为INT_MIN;

因为如果当所有的节点都为负数的时候，那么最终结果就为0，而不是其中最大的负数。

当然，面试的时候，这个问题是可以问清楚的，看看出题者的原意是什么，看看实际需要是什么，再处理。