学步园

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.

这道题其实跟求二叉树的深度类似，只不过需要求是带权值的深度而已，即所说的path sum。对于任意一个节点，其对应的path sum应该等于：其左子树节点的带权值深度 + 其右子树的带权值深度 + 其自身的值。而带权值的深度求法和一般的深度求法类似，就是取子节点带权值的深度的那个，加上自身的值即可。

这里需要注意的是，由于题目中没有说明所有节点的值都为非负数，所以得考虑负数的存在。如果一旦深度为负值，那么计算path sum的时候还不如不加子节点的带权值深度，所以这里每次计算出的带权值的深度，我都会跟0比较，如果比0小，那么我就取0。

// given a nonempty node, retrieve the weighted depth and update the max path sum
int weightedDepth(TreeNode *root, int & maxPathSum) {
	int leftPathSum = 0, rightPathSum = 0;
	if (root->left) leftPathSum = max(0, weightedDepth(root->left, maxPathSum));
	if (root->right) rightPathSum = max(0, weightedDepth(root->right, maxPathSum));
	// update the max path sum
	maxPathSum = max(maxPathSum, leftPathSum + root->val + rightPathSum);
	return max(leftPathSum + root->val, rightPathSum + root->val);
}
	    
int maxPathSum(TreeNode *root) {
	if (!root) return 0;
	int maxPathSum = INT_MIN;
	weightedDepth(root, maxPathSum);
	return maxPathSum;
}