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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
       
        if (root->left != 0 && root->right != 0)
        {
            int l = maxPathSum(root->left);
            int r = maxPathSum(root->right);

            int l1 = maxPathSum3(root->left);
            int r1 = maxPathSum3(root->right);

            int m1 = l1 + r1 + root->val;
            int m2 = l1 + root->val;
            int m3 = r1 + root->val;
            int m4 = root->val;
            int m5 = max(l, r);
            int m6 = max(l1, r1);
           
            return max(m1, max(m2, max(m3, max(m4, max(m5, m6)))));
        }
       
        if (root->left != 0)
        {
            int l = maxPathSum(root->left);
            int l1 = maxPathSum3(root->left);
           
            return max(l1, max(root->val, max(l1 + root->val, l)));
        }
       
        if (root->right != 0)
        {
            int r = maxPathSum(root->right);
            int r1 = maxPathSum3(root->right);
            return max(r1, max(root->val, max(r1 + root->val, r)));
        }
       
        return root->val;
    }
   
   
    int maxPathSum3(TreeNode* root) {
       
        if (root->left != 0 && root->right != 0)
        {
            int l = maxPathSum3(root->left);
            int r = maxPathSum3(root->right);

            return max(root->val, max(l, r) + root->val);
        }
       
        if (root->left != 0)
        {
            int l = maxPathSum3(root->left);
            return max(root->val, l + root->val);
        }
       
        if (root->right != 0)
        {
            int r = maxPathSum3(root->right);
            return max(root->val, r + root->val);
        }
       
        return root->val;
    }
   
    int max(int a, int b)
    {
        return a>b?a:b;
    }
     
};