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,

For example:

Given the below binary tree,

1
      / \
     2   3

Return 6.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    #define IMAX(x,y) (x>y?x:y)
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root)
        {
            return 0;
        }
        int left_sum = maxPathSum(root->left);
        int right_sum = maxPathSum(root->right);
        int sum = left_sum + root->val + right_sum;
        int m = IMAX(left_sum,right_sum);
        return IMAX(m,sum);
    }
};//the code above is wrong,think about it why?//we must keep the record maximum with root node,even if it is may not the whole max sum//below is the right code refer to [remlosttime]'s code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //we must return the max and the maximum path with root node
    int maxPathWithRoot(TreeNode * root,int &sum_with_root){
        if (!root){
            sum_with_root = 0;
            return 0;
        }
        if (!root->left && !root->right){
            sum_with_root = root->val;
            return root->val;
        }
        int left_max_sum = 0,left_with_root_max_sum = 0;
        int right_max_sum = 0,right_with_root_max_sum = 0;
        if (root->left){
            left_max_sum = maxPathWithRoot(root->left,left_with_root_max_sum);
        }else{
            left_max_sum = INT_MIN;
            left_with_root_max_sum = 0;
        }
        if (root->right){
            right_max_sum = maxPathWithRoot(root->right,right_with_root_max_sum);
        }else{
            right_max_sum = INT_MIN;
            right_with_root_max_sum = 0;
        }
        sum_with_root = max(left_with_root_max_sum + root->val,
                            max(right_with_root_max_sum + root->val,root->val));
        int sum = max(sum_with_root,
                      left_with_root_max_sum + right_with_root_max_sum + root->val);
        return max(sum,max(left_max_sum,right_max_sum));              

    }
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sum_with_root;
        return maxPathWithRoot(root,sum_with_root);

    }
};

原文链接: https://www.cnblogs.com/kwill/archive/2013/02/13/2910685.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍