Binary Tree Maximum Path Sum

LeetCode #124

Description:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example:

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

Idea:

Recursion. Return的时候只能return某一个子树，计算max path sum的时候需要both left and right.

Code:

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        max_sum_=INT_MIN;
        findMaxPathSum(root);
        return max_sum_;
    }

    int findMaxPathSum(TreeNode * root){
        if(root==NULL) return 0;
        int left_sum=findMaxPathSum(root->left);
        int right_sum=findMaxPathSum(root->right);
        int sum=root->val;
        if(left_sum>0) sum += left_sum;
        if(right_sum>0) sum += right_sum;

        max_sum_=max(max_sum_, sum);

        // Return时候只能return一颗子树，不能两颗同时return，
        // 这点与前一步计算max path sum不同
        return max(left_sum, right_sum)>0? root->val+max(left_sum, right_sum): root->val;
    }

private:
    int max_sum_;
};