Binary Tree Maximum Path Sum (Li

这道题算是Divide & Conquer中比较难的了。下面给出top down 和 bottom up 两种做法。

Top Down的做法是，对于每一点root，求出包含root->left的最大path sum，和包含root->right的最大path sum，将root->left, 与root->right的最大path sum分别与0比较，然后与root->val相加，就是root这一点的最大和。我们记录一个max_sum的全局变量，对于每一点都这么做，然后update 全局变量。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxPathSum(TreeNode * root) {
        // write your code here
        if(!root){
            return 0;
        }
        
        findMaxSum(root);
        return max_sum;
    }
    
    void findMaxSum(TreeNode *root){
        if(!root){
            return;
        }
        
        int leftSum = findUtil(root->left);
        int rightSum = findUtil(root->right);
        
        int curSum = root->val + max(0, leftSum) + max(0, rightSum);
        if(curSum > max_sum){
            max_sum = curSum;
        }
        
        findMaxSum(root->left);
        findMaxSum(root->right);
    }
    
    int findUtil(TreeNode *root){
        if(!root){
            return 0;
        }
        
        int left = findUtil(root->left);
        int right = findUtil(root->right);
        return root->val + max(0, max(left, right));
    }
    
private:
    int max_sum = INT_MIN;
};

Bottom Up的做法是自底向上扫一遍，而扫这一遍的过程中记录两个变量，一个是一该点为结尾的最大sum (singlePath sum)，一个是总共的最大sum。而途径该点(say, root) 的max path sum是由root->val + max(left.singlePaht, 0) + max(right.singlePath, 0) 求得的。total max sum需要打擂台，从下向上返回最大值。

Bottom Up的做法一开始并不好想，在实战时可以先给出Top Down的做法。这样便于推出Bottom Up的solution

struct ResultType{
        int singlePath, maxPath;
        ResultType(int s, int m):singlePath(s), maxPath(m){}
    };
    int maxPathSum(TreeNode *root) {
        // write your code here
        if(!root) return 0;
        ResultType rs = findSum(root);
        return rs.maxPath;
    }
    
    ResultType findSum(TreeNode *root){
        if(!root) return ResultType(0, INT_MIN);
        ResultType leftRs = findSum(root->left);
        ResultType rightRs = findSum(root->right);
        int singlePath = root->val + max(0, max(leftRs.singlePath, rightRs.singlePath));
        int maxPath = root->val + max(0, leftRs.singlePath) + max(0, rightRs.singlePath);
        int totalMax = max(maxPath, max(leftRs.maxPath, rightRs.maxPath));
        return ResultType(singlePath, totalMax);
    }