核心内容摘要
中文亚洲在线播：点亮全球影视的璀璨星河
思路本题和
二叉树的直径类似。
1链从下面的某个节点不一定是叶子节点到当前节点的路径这条链的节点值之和即为dfs的返回值。
如果节点值之和是负数则返回0因为要和0取最大值。
2直径等价于由两条或者一条链拼成的路径。
我们枚举每个node假设直径在这里“拐弯”也就是计算由左右两条从下面的某个节点不一定是叶子节点到node的链的节点值之和然后去更新答案的最大值。
注意dfs返回的是链的节点值之和不是直径的节点值之和。
疑问如果节点值都是负数会得出什么结果答如果所有节点值都是负数那么就是要求最大节点值即绝对值最小的负数。
因为在所有节点值都为负数的情况下路径中只有一个最大节点值即绝对值最小的负数是最优的毕竟随着节点数量的增多路径和只会减小此时求出来的最大路径和就是max(nums)。
递归三部曲
确定递归函数的参数和返回值类型1参数根节点root。
2返回值类型返回最大路径和为int类型。
3全局变量ans记录最大路径和。
private int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root)
确定终止条件如果节点为空则返回0。
不存在节点的话最大路径自然是0。
if(node null){ return 0; }
确定单层递归的逻辑因为求最大路径和要先知道左子树和右子树的链长因此采用后序遍历的顺序先递归左右子树再求最大路径和。
int left dfs(node.left); int right dfs(node.right); // 计算全局答案计算以当前节点为根的最大路径和因此可以返回两条链 ans Math.max(ans,left right node.val); // 是递归过程只需返回从左子树或右子树到当前节点的最大路径链给上层是告诉父节点从我这个节点往下走能得到的最大链和是多少 return Math.max(Math.max(left,right) node.val,
;复杂度分析1时间复杂度O(n)其中n为二叉树的节点个数。
2空间复杂度O(n)最坏情况下二叉树会退化成一条链递归需要O(n)的栈空间。
附代码class Solution { private int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node){ if(node null){ return 0; } int left dfs(node.left); int right dfs(node.right); // 计算全局答案计算以当前节点为根的最大路径和因此可以返回两条链 ans Math.max(ans,left right node.val); // 是递归过程只需返回从左子树或右子树到当前节点的最大路径链给上层是告诉父节点从我这个节点往下走能得到的最大链和是多少 return Math.max(Math.max(left,right) node.val,