leetcode——Binary Tree Maximum Path Sum

    这题很难，主要是我没理解题目的意思，后来看着给的测试参考，和网上找的答案，终于理解了。

例如： 给的

正确的路线应该是

也就是说，路径是一条的，不是有分叉的，之所以算出55是因为把>0的数都加上去了，这样路径就分叉了，就不是一条路径了，所以用dfs做时，返回值应该是左子树或者右子树中>0且比较大的那个子树的路径的值加上当前根节点的值。

我的是参考网上答案的代码：

// 用dfs，因为路径是任意的，所以根节点也是任意的，如果左子树的值>0，即对sum有贡献，则sum加其值，右子树的同理
// 在最后返回时，只能返回一个方向上的值，因为left-->root或者right—>root
class Solution {
private:
	int max_sum;
public:
	int maxPathSum(TreeNode *root) {
		max_sum = INT_MIN;
		dfs(root);
		return max_sum;
	}
	int dfs(TreeNode *root){
		if(root == NULL) return 0;
		int sum = root->val;
		int l = dfs(root->left);
		int r = dfs(root->right);
		if(l > 0) sum += l;
		if(r > 0) sum += r;
		max_sum = max(max_sum, sum);
		return max(l, r) > 0 ? max(l, r) + root->val : root->val;
	}
};

leetcode——Binary Tree Maximum Path Sum

原文：http://www.cnblogs.com/skysand/p/4222456.html