首页 > 代码库 > 新手算法学习之路----二叉树(二叉树最大路径和)
新手算法学习之路----二叉树(二叉树最大路径和)
摘抄自:https://segmentfault.com/a/1190000003554858#articleHeader2
题目:
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.
思路:首先我们分析一下对于指定某个节点为根时,最大的路径和有可能是哪些情况。第一种是左子树的路径加上当前节点,第二种是右子树的路径加上当前节点,第三种是左右子树的路径加上当前节点(相当于一条横跨当前节点的路径),第四种是只有自己的路径。乍一看似乎以此为条件进行自下而上递归就行了,然而这四种情况只是用来计算以当前节点根的最大路径,如果当前节点上面还有节点,那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值,一个是当前节点下最大路径和,另一个是如果要连接父节点时最大的路径和。我们用前者更新全局最大量,用后者返回递归值就行了。
Java代码:
public class Solution { private int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { helper(root); return max; } public int helper(TreeNode root) { if(root == null) return 0; int left = helper(root.left); int right = helper(root.right); //连接父节点的最大路径是一、二、四这三种情况的最大值 int currSum = Math.max(Math.max(left + root.val, right + root.val), root.val); //当前节点的最大路径是一、二、三、四这四种情况的最大值 int currMax = Math.max(currSum, left + right + root.val); //用当前最大来更新全局最大 max = Math.max(currMax, max); return currSum; } }
新手算法学习之路----二叉树(二叉树最大路径和)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。