更新时间：2025-04-04
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3*10^4]-1000 <= Node.val <= 1000
方法：递归法（后序遍历）
通过后序遍历计算每个节点的最大贡献值，并更新全局最大路径和。
- 每个节点计算其左右子树的最大贡献值（若贡献为负则取0）。
- 当前节点的总路径和为
自身值 + 左贡献 + 右贡献，更新全局最大值。 - 返回当前节点能为父节点提供的单边最大贡献（即
自身值 + max(左贡献, 右贡献)）。
代码实现(Java)：
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode node) {
if (node == null) return 0;
// 计算左右子树的贡献值，负数则舍弃
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 当前节点作为路径中间节点的总路径和
int currentPathSum = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, currentPathSum);
// 返回当前节点能提供的最大单边贡献（给父节点使用）
return node.val + Math.max(leftGain, rightGain);
}
}
复杂度分析
- 时间复杂度：
O(n)，所有节点仅访问一次。 - 空间复杂度：
O(h)，递归栈深度（h为树的高度，最坏情况下为O(n)）。
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：
输入：nums = [1,0,1,2]
输出：3
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
方法：哈希集合优化
利用哈希集合存储所有数字，仅对可能的连续序列起点进行检查，避免重复计算。
- 去重存储：将所有数字存入哈希集合，去除重复。
- 查找起点：遍历集合中的元素，若当前数字的前驱
（num-1）不在集合中，则视为序列起点。 - 扩展序列：从起点开始逐个查找后续数字，计算当前连续序列长度。
- 更新结果：记录遍历过程中的最大序列长度。
代码：
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int maxLength = 0;
for (int num : numSet) {
// 只有当num是序列起点（前驱不存在）时才处理
if (!numSet.contains(num - 1)) {
int currentNum = num;
int currentLength = 1;
// 向后扩展序列
while (numSet.contains(currentNum + 1)) {
currentNum++;
currentLength++;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}
}
复杂度分析：
- 时间复杂度：
O(n)。每个元素最多被访问两次（加入集合和扩展序列）。 - 空间复杂度：
O(n)。哈希集合存储所有元素。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。