java编程求二叉树最大路径问题代码分析
作者:Felix Fang 时间:2023-03-16 20:44:16
题目:
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为总节点数。
总结
来源:https://www.cnblogs.com/felixfang/p/3637984.html
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java动态绑定和静态绑定用法实例详解
Java读取properties文件之中文乱码问题及解决
![](https://img.aspxhome.com/file/2023/1/73051_0s.jpg)
.net的序列化与反序列化实例
java对接支付宝支付接口开发详细步骤
![](https://img.aspxhome.com/file/2023/4/58744_0s.jpg)
Java多线程模拟银行系统存钱问题详解
![](https://img.aspxhome.com/file/2023/4/60254_0s.jpg)
SpringBoot解决跨域请求拦截问题代码实例
![](https://img.aspxhome.com/file/2023/4/67964_0s.png)
Springboot整合MybatisPlus的实现过程解析
c#入门之分支语句使用方法(三元运算符、if语句、switch语句)
Java使用新浪微博API通过账号密码方式登陆微博的实例
Android使用Intent隐式实现页面跳转
![](https://img.aspxhome.com/file/2023/5/93285_0s.png)
java算法实现预测双色球中奖号码
spring框架集成flyway项目的详细过程
![](https://img.aspxhome.com/file/2023/7/70307_0s.jpg)
C#实现飞行棋(Winform)
![](https://img.aspxhome.com/file/2023/9/96399_0s.jpg)
C#访问SqlServer设置链接超时的方法
Android之Gallery使用例子
![](https://img.aspxhome.com/file/2023/0/96770_0s.png)
spring boot微服务场景下apollo加载过程解析
解决@Transactional注解事务不回滚不起作用的问题
C#游戏开发之实现华容道游戏
![](https://img.aspxhome.com/file/2023/8/75588_0s.jpg)
Android学习之Broadcast的简单使用
使用java打印心型、圆形图案的实现代码
![](https://img.aspxhome.com/file/2023/9/66649_0s.jpg)