124. The maximum path in a binary tree and

Difficulty 1426
route It is defined as a path starting from any node in the tree , Along the parent node - Child node connection , A sequence that reaches any node . The same node in a path sequence At most once . This path At least one node , And it doesn't have to go through the root node .
Path and Is the sum of the values of the nodes in the path .
Give you the root node of a binary tree root , Back to its The maximum path and .

Example 1：

Input ：root = [1,2,3] Output ：6 explain ： The best path is 2 -> 1 -> 3 , Path and are 2 + 1 + 3 = 6
Example 2：

Input ：root = [-10,9,20,null,null,15,7] Output ：42 explain ： The best path is 15 -> 20 -> 7 , Path and are 15 + 20 + 7 = 42

Tips ：

• The range of nodes in the tree is [1, 3 * 104]
• -1000 <= Node.val <= 1000

Ideas

• Failure thinking : In the sequence traversal , Set global variables , Accumulate during traversal ( Path selection is not considered : Up or right )
  
  

Code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
    
        if (node == nullptr) {
    
            return 0;
        }
        
        //  Recursively calculate the maximum contribution value of left and right child nodes 
        //  Only when the maximum contribution value is greater than  0  when , The corresponding child node will be selected 
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        //  The maximum path sum of a node depends on the value of the node and the maximum contribution value of its left and right children ( Left middle right )
        int priceNewpath = node->val + leftGain + rightGain;

        //  Update answers 
        maxSum = max(maxSum, priceNewpath);

        //  Returns the maximum contribution value of the node ,( Continue to find the parent node )
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
    
        maxGain(root);
        return maxSum;
    }
};