这篇文章给大家分享的是有关java中如何求二叉树最大路径的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
题目：
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.
节点可能为负数，寻找一条最路径使得所经过节点和最大。路径可以开始和结束于任何节点但是不能走回头路。
这道题虽然看起来不同寻常，但是想一下，可以发现不外乎二叉树的遍历+简单的动态规划思想。
我们可以把问题拆分开：即便最后的最大路径没有经过根节点，它必然也有自己的“最高点”，因此我们只要针对所有结点，求出：如果路径把这个节点作为“最高点”，路径最长可达多少？记为max。然后在max中求出最大值MAX即为所求结果。和“求整数序列中的最大连续子序列”一样思路。
下面就是找各个“最高点”对应的max之间的关系了。
我们拿根节点为例，对于经过根节点的最大路径的计算方式为：
我们找出左子树中以左孩子为起点的最大路径长度a，和右子树中以右孩子为起点的最大路径长度b。然后这个点的max=MAX(a+b+node.val,a+node.val,b+node.val,node.val)
因此我们定义一个函数来算上面的a或者b，它的参数是一个节点，它的返回值是最大路径长度，但是这个路径的起点必须是输入节点，而且路径必须在以起点为根节点的子树上。
那么函数func(node)的return值可以这样定义：returnMAX(func(node.left)+node.val,func(node.right)+node.val,node.val)
终止条件是node==null，直接返回0。
接着我们发现上述计算max和求出MAX的过程完全可以放到func(node)里去。
按照这个思路的代码，maxPathSumCore就是上面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;
}
;时间复杂度 O(n)，n为总节点数。
感谢各位的阅读！关于“java中如何求二叉树最大路径”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
