LeetCode OJ 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.

int max(int a, int b) {
	if (a > b) return a;
	return b;
}

int ans;

int maxDownSum(struct TreeNode * now) {
	if (!now) return 0;
	int l = max(0, maxDownSum(now->left));
	int r = max(0, maxDownSum(now->right));
	ans = max(ans, l + r + now->val);
	return max(l, r) + now->val;
}

int maxPathSum(struct TreeNode * root) {
	ans = INT_MIN;
	maxDownSum(root);
	return ans;
}

LeetCode OJ Binary Tree Maximum Path Sum

原文：http://blog.csdn.net/u012925008/article/details/44782685