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.

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum/

Discussion

这种题必须根据一个实例coding。最大值有可能在任意node取得，有可能包含左右子树的maxSum（如果都大于0的话），也有可能都不包含。而每个node返回的值一定是它本身的值加上左右子树maxSum大的那个，在每个node返回的路径是只能包含一个子树的。注意区分就没有问题了。

Solution

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxPathSum(TreeNode *root) {
        // write your code here
        int maxSum = INT_MIN;
        findMax(root, maxSum);
        return maxSum;
    }
private:
    int findMax(TreeNode *root, int &maxVal) {
        if(root == NULL) return 0;
        int l = findMax(root->left, maxVal); 
        int r = findMax(root->right, maxVal);
        int cur = root->val;
        if(l > 0) cur+=l;
        if(r > 0) cur+=r;
        maxVal  = max(maxVal, cur);//更新maxSum
        return root->val + max(l, r);//返回该节点的单个路径的最大值
    }
};