leetcode hot100【LeetCode 124.二叉树中的最大路径和】java实现

LeetCode 124.二叉树中的最大路径和

题目描述

给定一个非空二叉树，返回其最大路径和。路径定义为从树中任意节点出发，到达任意节点的有向边序列。该路径至少包含一个节点，且不需要在根节点开始或结束。

示例 1:

输入: tree = [1,2,3]1/ \2   3
输出: 6

解释: 最大路径和为 2 + 1 + 3 = 6。

示例 2:

输入: tree = [-10,9,20,null,null,15,7]-10/  \9   20/  \15   7
输出: 42

解释: 最大路径和 = 15 + 20 + 2 = 42。

Java 实现代码

class Solution {private int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {calculateMaxPathSum(root);return maxSum;}private int calculateMaxPathSum(TreeNode node) {if (node == null) {return 0;}// 计算左子树的最大单侧路径和，负值取0int leftMax = Math.max(0, calculateMaxPathSum(node.left));// 计算右子树的最大单侧路径和，负值取0int rightMax = Math.max(0, calculateMaxPathSum(node.right));// 计算经过当前节点的路径和int currentPathSum = node.val + leftMax + rightMax;// 更新全局最大路径和maxSum = Math.max(maxSum, currentPathSum);// 返回当前节点的单侧最大路径和return node.val + Math.max(leftMax, rightMax);}
}

解题思路

递归后序遍历:

对于每个节点，我们需要计算：
通过该节点的路径贡献值（即该节点与其左右子树的最大单侧路径和）。
经过该节点的最大路径和（即左子树最大路径和 + 当前节点值 + 右子树最大路径和）。

全局最大值更新:

用一个全局变量记录二叉树中的最大路径和，每次递归过程中动态更新。

返回值:

对于每个节点，递归函数返回以该节点为起点的最大单侧路径和。

复杂度分析

时间复杂度：O(n) 每个节点只访问一次，因此时间复杂度为 O(n)，其中 n 是节点总数。

空间复杂度：O(h) 递归调用栈的空间复杂度为 O(h)，其中 h 是二叉树的高度。在最坏情况下，h = O(n)（完全不平衡树）。

示例树结构
     1/    \3       5/ \     /   \
6   7  8     2 
目标：求二叉树中的最大路径和

最大路径和的定义：

路径：路径必须至少包含一个节点，路径可以从树中的任意节点出发，经过父子连接，最终到达任意节点。
路径和：路径上所有节点的值的和。
最大路径和：树中的所有路径中，路径和最大的那个值。

递归计算每个节点的贡献
节点 6：
6 没有左右子树，因此返回 6。
对于节点 6，它的最大路径和贡献就是它本身的值：
leftMax = 0, rightMax = 0
currentPathSum = 6
return 6 (返回以 `6` 为起点的最大路径和)
节点 7：
7 没有左右子树，因此返回 7。
对于节点 7，它的最大路径和贡献也是它本身：
leftMax = 0, rightMax = 0
currentPathSum = 7
return 7 (返回以 `7` 为起点的最大路径和)
节点 3：
计算节点 3 的最大路径和：
左子树返回 6。
右子树返回 7。

currentPathSum = 3 + 6 + 7 = 16，它是通过节点 3 经过 6 和 7 的最大路径和。
但是 3 也可以选择只通过左子树或右子树，因此返回的最大路径和是：
currentPathSum = 3 + 6 + 7 = 16
return 3 + max(6, 7) = 3 + 7 = 10 (返回以 `3` 为起点的最大路径和)
更新全局最大路径和 maxSum 为 16。
节点 8：
8 没有左右子树，因此返回 8。
对于节点 8，它的最大路径和贡献就是它本身：
leftMax = 0, rightMax = 0
currentPathSum = 8
return 8 (返回以 `8` 为起点的最大路径和)
节点 2：
2 没有左右子树，因此返回 2。
对于节点 2，它的最大路径和贡献就是它本身：
leftMax = 0, rightMax = 0
currentPathSum = 2
return 2 (返回以 `2` 为起点的最大路径和)
节点 5：
计算节点 5 的最大路径和：
左子树返回 8。
右子树返回 2。

currentPathSum = 5 + 8 + 2 = 15，它是通过节点 5 经过 8 和 2 的最大路径和。
但是 5 也可以选择只通过左子树或右子树，因此返回的最大路径和是：
currentPathSum = 5 + 8 + 2 = 15
return 5 + max(8, 2) = 5 + 8 = 13 (返回以 `5` 为起点的最大路径和)
节点 1（根节点）：
计算节点 1 的最大路径和：
左子树返回 10（从 3 节点传递过来的最大路径和）。
右子树返回 13（从 5 节点传递过来的最大路径和）。

currentPathSum = 1 + 10 + 13 = 24，它是通过节点 1 经过左子树 10 和右子树 13 的最大路径和。
但是 1 也可以选择只通过左子树或右子树，因此返回的最大路径和是：
currentPathSum = 1 + 10 + 13 = 24
return 1 + max(10, 13) = 1 + 13 = 14 (返回以 `1` 为起点的最大路径和)
更新全局最大路径和 maxSum 为 24。
全局最大路径和：通过上述递归计算，我们得到了整个树中的最大路径和 24，路径是： 6 -> 3 -> 1 -> 5 -> 8