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.

分析：这道题的难点在于路径可以是任意路径而不限于从根开始。解决这个问题我们可以从分解问题和分类讨论入手。对于一个二叉树，其maximum path或者包含root，或者不包含root，这点是解决问题的关键。如果maximum path不包含root，那么这个问题就分解成求左右两个子树的maximum path sum，然后取大的。如果maximum path包含root，我们在计算maximum path sum时需要知道包含左子树中包含root->left的maximum path sum（这里用left_sum表示）和右子树中包含root->right的maximum path sum（用right_sum表示）。我们用maxsum表示题目要求的maximum path sum，如果left_sum和right_sum均小于等于0，那么maxsum = max(maxsum, root->val)；否则maxsum取当前maxsum、left_sum+root->val, right_sum+root->val, left_sum+root->val+right_sum的最大值。至此，这道题就可以解决了。代码如下：

class Solution {public:    int maxPathSum(TreeNode *root) {        int max_sum = INT_MIN;        max_path(root, max_sum);        return max_sum;    }        int max_path(TreeNode * root, int & max_sum){        if(root == NULL) return 0;                int l = max_path(root->left, max_sum);        int r = max_path(root->right, max_sum);        int sum = root->val;                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