124. Maximum path sum in binary trees

Make writing a habit together! This is the third day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

A path is defined as a sequence that starts at any node in the tree and follows parent to child nodes to reach any node. The same node appears at most once in a path sequence. The path contains at least one node and does not necessarily go through the root node.

Path and is the sum of the values of all nodes in a path.

Give you the root node of a binary tree, root, return its maximum path and.

Thought analysis

As a difficult problem, it’s not that difficult. Although the problem gives any node, which is connected by any path, it also means that for a path, we can also understand that the highest parent node of the path extends to the left and right two times (of course, there may only be one).

So, how do you calculate the maximum left and right extension of a node?

It just keeps recursing, based on the maximum value of the left and right subtrees plus their value, and when the left and right subtrees are less than 0, exclude.

The specific implementation

int maxPathSum(TreeNode* root) {
        return dfs(root);
    }
    int dfs(TreeNode* node){
        if (node == nullptr)return 0;
        int val = node -> val;
        int leftvalue = max(0.dfs(node->left));
        int rightvalue = max(0.dfs(node -> right));
        
        return max(max(max(0, val + leftvalue + rightvalue), leftvalue), rightvalue);
    }
Copy the code

So write, find wrong

Consider all negative numbers. To rethink the logic, we are now calculating the maximum contribution of the left and right subtrees by default, which means that we can allow both the left and right subtrees to be zero in this calculation. The root node must also be used by default.

There is a loophole, which is that if our path does not end up passing the root node, the maximum value needs to be saved by an extra global variable.

conclusion

The idea is written, it will not post a code.