Code analysis of finding the maximum path of binary tree by Java programming

Title:

Binary Tree Maximum Path Sum

Given a binary tree,find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,

Return 6.

Nodes may be negative. Find the most path to maximize the sum of nodes. A path can start and end at any node, but it cannot go back.

Although this problem looks unusual, if you think about it, you can find that it is nothing more than traversal of binary tree + simple dynamic programming idea.

We can split the problem: even if the last maximum path does not pass through the root node, it must have its own "highest point". Therefore, we just need to find out for all nodes: if the path takes this node as the "highest point", how long can the path be? Mark it as max. Then find the maximum value in Max, which is the result. The same idea as "finding the largest continuous subsequence in an integer sequence".

Here is the relationship between Max corresponding to each "highest point".

Taking the root node as an example, the maximum path through the root node is calculated as follows:

We find the maximum path length a starting from the left child in the left subtree and the maximum path length B starting from the right child in the right subtree. Then max of this point = max (a + B + node.val, a + node.val, B + node.val, node. VAL)

Therefore, we define a function to calculate the above a or B. its parameter is a node, and its return value is the maximum path length, but the starting point of the path must be the input node, and the path must be on the subtree with the starting point as the root node.

The return value of func (node) can be defined as returnmax (func (node. Left) + node val,func(node.right)+node. val,node. val)

The termination condition is node = = null, and 0 is returned directly.

Then we find that the above process of calculating Max and finding Max can be put into func (node).

According to the code of this idea, maxpathsumcore is the implementation of func (node) above:

Time complexity O (n), n is the total number of nodes.