“This is the 24th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

The maximum path sum in a binary tree

The maximum path sum in binary trees

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

The sample

Example 1

Input: root = [1,2,3] Output: 6 Description: The optimal path is 2 -> 1 -> 3, and the sum of paths is 2 + 1 + 3 = 6Copy the code

Example 2

Input: root = [-10,9,20, NULL, NULL,15,7] Output: 42 Description: The optimal path is 15 -> 20 -> 7, and the sum of paths is 15 + 20 + 7 = 42Copy the code

Tip:

  • The number of nodes in the tree ranges from[1, 3 * 10 ^ 4)
  • 1000 <= Node.val <= 1000

The problem solving

Solution one: recursion

Train of thought

The binary tree path is

  1. You start at any node, you go to any node
  2. The path contains at least one node and does not necessarily go through the root node

For example, 4 → 2 → 1 → 3; Or 6 goes to 3 goes to 7; Or there’s only one node 2 on the path

As you can see, the difference between this path and binary tree is:

  • A node in a binary tree that is joined by a parent node to the left and right child nodes
  • In a path, the path is one node, and you can only go in two directions.

In the case of node 2, path 2 has the following three situations:

  1. Left + right
  2. + left on
  3. + on the right

Let’s say we start from the bottom up.

  • Only one child node can be selected
  • When you come to a parent node, you can tell the parent node what its value is, and the parent node will take the value of the child node and compare it with another child node, select the larger child node to add to itself, and then continue to go up
  • Or if you can’t go any further, you turn to connect the left and right child nodes

With the general idea above, you should have the idea of solving the problem

Let’s say I have a binary tree element

  • A is the root node, connected to the upper parent node (assuming one exists)

  • B and C are child nodes connected to the node with the maximum path in their respective child nodes

  • All possible paths

    • Left right b + a + c
    • B + a left
    • C + a right

Choose left or right? We can define a function that calculates the maximum sum of paths from the current node to the lower node

When you pass a in, you need to know the maximum sum of paths b and C can take down, you just recurse over b and C, get the return value, take the larger one, add the value of A, and you get the maximum sum of paths A can take down. It is important to note that the answer is not the return value of the root node because the maximum path sum of the entire binary tree does not necessarily go through the root node. So you need a global variable that can record the maximum value of the sum of all paths, and when you get the maximum sum of a path, you update it into the global maximum sum

  • Recursively call b and C
  • Compute b+a and C +a, choosing the larger value as the return value
  • Update to the global maximum sum

If the node value is negative, the negative value should be discarded as much as possible to maximize the sum (Max (0, x) can be used). Note that a cannot be discarded as a must, either to continue up or to join B and C (in case all nodes are negative, the code will not get the correct result)

code

Func maxPathSum(root *TreeNode) int {maxSum := math.minint64 var maxValue func(*TreeNode) int MaxValue = func(node *TreeNode) int {// Used to calculate the maximum path to the bottom of a node and if node == nil {return 0} leftValue := Max (maxValue(node.left), 0) // rightValue := Max (maxValue(node.right), 0) priceNewPath := node.Val + leftValue + rightValue MaxSum = Max (priceNewPath, maxSum) return node.Val + Max (leftValue, } maxValue(root) return maxSum} func Max (x, y int) int { if x > y { return x } return y }Copy the code