时间:2021-05-19
题目:
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.
节点可能为负数,寻找一条最路径使得所经过节点和最大。路径可以开始和结束于任何节点但是不能走回头路。
这道题虽然看起来不同寻常,但是想一下,可以发现不外乎二叉树的遍历+简单的动态规划思想。
我们可以把问题拆分开:即便最后的最大路径没有经过根节点,它必然也有自己的“最高点”,因此我们只要针对所有结点,求出:如果路径把这个节点作为“最高点”,路径最长可达多少?记为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编程求二叉树最大路径问题代码分析的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Java实现打印二叉树所有路径的方法。分享给大家供大家参考,具体如下:问题:给一个二叉树,把所有的路径都打印出来。比如,对于下面这个二叉树,它所有
问题如何遍历一个二叉树遍历二叉树就是访问二叉树的每一个节点二叉树父结点下先左访问,先序遍历(根左右)例如:遍历以下的二叉树遍历结果:ABDECFPython代码
给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像。仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤。这两棵树的根节点相同,但他们的左右两个
什么是二叉树,这里不再介绍,可以自行百度:二叉树。在这里利用java实现“表达式二叉树”。表达式二叉树的定义第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表
二叉树的一些概念二叉树就是每个结点最多有两个子树的树形存储结构。先上图,方便后面分析。1满二叉树和完全二叉树上图就是典型的二叉树,其中左边的图还叫做满二叉树,右