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