The title

Given a nonempty binary tree, return its maximum path sum.

In this case, a path is defined as a sequence that starts at any node in the tree and reaches any node. The path contains at least one node and does not necessarily go through the root node.

The sample1: Input: [1.2.3]

       1
      / \
     2   3Output:6
Copy the code
The sample2: Input: [- 10.9.20,null,null,15.7]

   - 10
   / \
  9  20
    /  \
   15   7Output:42
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Difficulty factor: Difficulty

Ideas (DFS)

First, consider implementing a simplified function maxGain(node), which calculates the maximum contribution value of a node in the binary tree. Specifically, it looks for a path starting from the node in the subtree with the node as the root, maximizing the sum of the node values on the path.

Specifically, the function is evaluated as follows.

The maximum contribution of an empty node is equal to 000. The maximum contribution of a non-empty node is equal to the sum of the node value and the maximum contribution of its children (for leaf nodes, the maximum contribution is equal to the node value).Copy the code

For example, consider the following binary tree.

   - 10
   / \
  9  20
    /  \
   15   7
Copy the code

The maximum contribution values of leaf nodes 9, 15 and 7 were 9, 15 and 7, respectively.

After the maximum contribution value of leaf node is obtained, the maximum contribution value of non-leaf node is calculated. The maximum contribution of node 20 is 20+ Max ⁡(15,7)=35, and that of node −10 is −10+ Max ⁡(9,35)=25.

The above calculation process is recursive. Therefore, the maximum contribution value of each node can be obtained by calling the function maxGain on the root node.

After obtaining the maximum contribution value of each node according to the function maxGain, how to obtain the maximum path sum of the binary tree? For a node in the binary tree, the maximum path sum of the node depends on the value of the node and the maximum contribution value of the left and right child nodes of the node. If the maximum contribution value of the child node is positive, the maximum path sum of the node is included; otherwise, the maximum path sum of the node is not included. Maintain a global variable maxSum to store the maximum path sum, update the value of maxSum in the recursive process, and finally get the value of maxSum is the maximum path sum in the binary tree.

Author: Leetcode-Solution Link: leetcode-cn.com/problems/bi… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Code implementation

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        // Calculate the maximum contribution of the left and right child nodes recursively
        // The child node is selected only when the maximum contribution value is greater than 0
        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 of the left and right children of the node
        int priceNewpath = node->val + leftGain + rightGain;

        // Update the answer
        maxSum = max(maxSum, priceNewpath);

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

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        returnmaxSum; }}; > Author: Leetcode-solution > Link: HTTPS:/ / leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/ sources: LeetCode copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.
Copy the code

Complexity analysis

Time complexity: O(N), where N is the number of nodes in the binary tree. Each node is accessed no more than twice. Space complexity: O(N), where NNN is the number of nodes in the binary tree. Spatial complexity depends primarily on the number of recursive call layers, with the maximum number of layers equal to the height of the binary tree and the worst case equal to the number of nodes in the binary tree.Copy the code

Author: Leetcode-Solution Link: leetcode-cn.com/problems/bi… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.