leetcode 124. 二叉树中的最大路径和

递归

递归函数计算每一个结点向下延伸（可能是左或者右）的最大和路径，作为每次递归的返回值
用一个全局的 maxret 记录最后的答案，递归达到叶子返回的时候不断跟新maxret
由于每次计算该节点的时候需要计算左子树和右子树的最大，所以就可以直接计算该点连接左右子数的最大路径和，然后去更新maxret
递归从叶子开始往上构造，类似求最大子序列的和，当前叶子的孩子的和如果是个负数就丢弃掉，重新计算和，如果大于零就加上之后返回

class Solution {
public:
    int maxret = INT_MIN;
    int maxPathSum(TreeNode* root) {
        findMax(root);
        return maxret;
    }
    int findMax(TreeNode* root){
        if(!root){
            maxret = max(maxret,0);
            return 0;
        }
        if(!root->left && !root->right){
            maxret = max(maxret,root->val);
            return root->val;
        }else if(root->left && !root->right){
            int lmax = findMax( root->left );
            if(lmax <= 0){
                maxret = max(maxret,root->val);
                return root->val;
            }else{
                maxret = max(maxret,lmax + root->val);
                return lmax + root->val;
            }
        }else if(!root->left && root->right){
            int rmax = findMax( root->right );
            if(rmax <= 0){
                maxret = max(maxret,root->val);
                return root->val;
            }else{
                maxret = max(maxret,rmax + root->val);
                return rmax + root->val;
            }
        }else{
            int rootval = root->val;
            int lmax = findMax( root->left );
            int rmax = findMax( root->right );
            int max1 = max(lmax,rmax);
            int tempret = rootval;
            if(lmax>0){
                tempret += lmax;
            }
            if(rmax >0){
                tempret += rmax;
            }
            if(max1 > 0){
                rootval += max1;
            }

            maxret = max(maxret,tempret);
            return rootval;
        }
    }

};