当前位置：首页 > news >正文

050二叉树中的最大路径和

news 2026/6/4 16:10:34

二叉树中的最大路径和

题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-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意味着不选取这个子节点，直接避开了不同情况的讨论和溢出问题，编码简单，思路清晰易懂。