二叉树中的最大路径和题目链接https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } public int dfs(TreeNode cur){ if(cur null){ return Integer.MIN_VALUE; } int leftMax dfs(cur.left); int rightMax dfs(cur.right); int maxNotCur Math.max(leftMax, rightMax);//不包含当前节点时的路径最大值 ans Math.max(ans, maxNotCur); int max;//包含当前节点时的路径最大值 if(leftMax Integer.MIN_VALUE rightMax Integer.MIN_VALUE){//当前节点为叶子节点 max cur.val; } else if(leftMax Integer.MIN_VALUE || rightMax Integer.MIN_VALUE){//当前节点的左孩子或右孩子为空 max cur.val maxNotCur; } else{ max cur.val Math.max(maxNotCur, leftMax rightMax);//当前节点的左孩子和右孩子都不为空 } max Math.max(max, cur.val); ans Math.max(ans, max); return maxNotCur 0 ? cur.val maxNotCur : cur.val; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路遍历二叉树每次递归获取当前节点左子树的最大路径和一定包含当前节点的左孩子与右子树的最大路径和一定包含当前节点的右孩子每次遍历用全局变量ans记录答案对于每个节点需要进行两种情况的答案比较第一种情况是不包含当前节点另一种情况是包含当前节点。 情况一不包含当前节点取当前节点左、右子树的最大路径和较大的那个值与答案作比较即可 情况二包含当前节点对于这种情况我们需要注意溢出问题当前节点的左孩子或右孩子为空时值相加会导致溢出所以需要按左、右孩子是否为空分三种情况讨论。将三种不同情况得出的最大值与当前节点的值作比较取最大值并与答案作比较即可。 注意递归方法最后返回的当前节点的最大路径和一定是包含当前节点的情况且不能是既包含左孩子又包含右孩子的情况。看了官方题解后的解答public int ans Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return ans; } public int maxGain(TreeNode cur){ if(cur null){ return 0; } //只有在最大贡献值大于 0 时才会选取对应子节点 int leftGain Math.max(maxGain(cur.left), 0);//左孩子的最大贡献值 int rightGain Math.max(maxGain(cur.right), 0);//右孩子的最大贡献值 int curGain cur.val leftGain rightGain;//节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值 ans Math.max(ans, curGain); //返回节点的最大贡献值 return cur.val Math.max(leftGain, rightGain); }分析 1、代码的时间复杂度为O(n)空间复杂度为O(n)。 2、解题思路对于每一个节点而言节点的最大路径和取决于该节点的值与该节点的左、右子节点的最大贡献值且只有在最大贡献值大于0时才会选取对应子节点。 3、我的解答与官方解答的区别主要区别在于对当前节点的左、右子节点的最大贡献值小于0时的处理方法。我用了分情况讨论所以编码较为复杂而官方题解直接将贡献度小于0的赋值为0贡献度为0意味着不选取这个子节点直接避开了不同情况的讨论和溢出问题编码简单思路清晰易懂。总结本题的关键在于总结出“节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值”这个结论以及节点的贡献值为负数时如何处理。
