topic:
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,
1 / / 2 3
Return 6.
The node may be negative, looking for a most path so that the nodes passed through are the largest. The path can start and end at any node but cannot go back.
Although this question looks unusual, if you think about it, you will find that it is nothing more than traversal of binary trees + simple dynamic planning ideas.
We can separate the problem: even if the last largest path does not pass through the root node, it must have its own "highest point". Therefore, we only need to find out for all nodes: If the path takes this node as the "highest point", what is the maximum length of the path? Note as max. Then find the maximum value MAX in max, which is the result you are looking for. The same idea as "finding the largest continuous subsequence in an integer sequence".
The following is to find the relationship between max corresponding to each "highest point".
Let’s take the root node as an example. The calculation method for the maximum path passing through the root node is:
We find the maximum path length a in the left subtree with the left child as the starting point, and the maximum path length b in the right subtree with the right child as the starting point. Then the max=MAX of this point(a+b+node.val,a+node.val,b+node.val,node.val)
Therefore, we define a function to calculate a or b above. Its parameter is a node, and its return value is the maximum path length. However, the starting point of this path must be the input node, and the path must be on a subtree with the starting point as the root node.
Then the return value of the function func(node) can be defined as follows: returnMAX(func(node.left)+node.val,func(node.right)+node.val,node.val)
The termination condition is node==null, and it returns 0 directly.
Then we found that the above process of calculating max and calculating MAX can be completely put into func(node).
According to the code of this idea, maxPathSumCore is the above implementation of func(node):
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int maxPathSum(TreeNode *root) {maxPathSumCore(root);return MAX;}int maxPathSumCore(TreeNode *node) {if(NULL == node) return 0;int a = maxPathSumCore(node -> left);int b = maxPathSumCore(node -> right);if((a+b+node->val) > MAX) MAX = (a+b+node->val);if((a+node->val) > MAX) MAX = (a+node->val);if((b+node->val) > MAX) MAX = (b+node->val);if(node->val > MAX) MAX = node->val;int maxViaThisNode = ((a + node->val) > node->val ? (a + node->val) : node->val);return (maxViaThisNode > (b + node->val) ? maxViaThisNode : (b + node->val));}private: int MAX= -99999999;};Time complexity O(n), n is the total number of nodes.
Summarize
The above is the entire content of this article about the code analysis of the maximum path of the binary tree in Java programming. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!