【LeetCode 热题 100】124. 二叉树中的最大路径和——DFS
Problem: 124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(H)
整体思路
这段代码旨在解决一个高难度的二叉树问题：二叉树中的最大路径和 (Binary Tree Maximum Path Sum)。这里的“路径”被定义为从树中任意节点到任意节点的序列，路径中至少包含一个节点，且不一定需要经过根节点。
该算法采用了一种精巧的 后序遍历 (Post-order Traversal) 递归思想。算法的核心在于，dfs 递归函数承担了双重职责：
-
职责一：更新全局最大路径和
- 在每次访问一个节点
node时，它都将该节点视为一个潜在的“路径转折点”或“拱顶”。 - 以
node为转折点的路径，其最大和可以由node.val加上从左子树贡献的最大“向下”路径和left，再加上从右子树贡献的最大“向下”路径和right构成。即sum = node.val + left + right。 - 这个
sum值代表了一个完整的、可能横跨左右子树的路径，它是一个全局最大路径和的候选者。因此，代码用ans = Math.max(ans, sum)来随时更新全局最大值ans。
- 在每次访问一个节点
-
职责二：向父节点贡献“单边”路径
- 当
dfs(node)完成计算后，它需要返回一个值给它的父节点。这个返回值不能是上面计算的“拱形”路径和sum，因为一条路径不能分叉。 - 它必须返回一个从
node出发，一路向下的“单边”路径的最大和。这个单边路径要么走向左子树，要么走向右子树。 - 因此，它计算
Math.max(left, right) + node.val，选择左右两条单边路径中较大的一条，并加上当前节点的值。 - 关键的剪枝：如果这个计算出的最佳“单边”路径和是负数，那么它对父节点来说只会起到负面作用。在这种情况下，父节点还不如不包含这条路径。因此，函数最终返回
Math.max(..., 0)，即如果贡献为负，则贡献一个0。
- 当
通过这种后序遍历，每个节点都能利用其子节点计算出的“单边最大贡献”，来计算以自身为“拱顶”的全局路径和，并同时计算出能向上贡献给父节点的新的“单边最大贡献”。
完整代码
class Solution {// ans: 全局变量，用于存储和更新在整个树中找到的最大路径和。// 初始化为整数的最小值，以确保任何路径和（包括负数）都能正确地更新它。private int ans = Integer.MIN_VALUE;/*** 主函数：启动递归计算并返回最终的最大路径和。* @param root 树的根节点* @return 树中的最大路径和*/public int maxPathSum(TreeNode root) {// 调用递归辅助函数，该函数会通过副作用（修改 ans）来计算结果。dfs(root);// 返回全局最大值。return ans;}/*** 递归辅助函数 (DFS)。* 该函数有两个职责：* 1. 计算以 `node` 为“转折点”的最大路径和，并用它更新全局 `ans`。* 2. 返回从 `node` 出发向下的“单边”路径的最大和，作为对父节点的贡献。* @param node 当前访问的节点* @return 从 `node` 出发的单边路径的最大贡献值（非负）。*/private int dfs(TreeNode node) {// 递归的终止条件：如果节点为空，其贡献的路径和为0。if (node == null) {return 0;}// 后序遍历：先递归计算左右子树的贡献。// left: 从左子节点出发的单边路径的最大贡献值（已经过 max(..., 0) 处理，非负）。int left = dfs(node.left);// right: 从右子节点出发的单边路径的最大贡献值（非负）。int right = dfs(node.right);// 【职责一】计算以当前 node 为“拱顶”的路径和。// 这条路径连接了左、右子树贡献的最大单边路径。int sum = left + right + node.val;// 用这个“拱形”路径和去更新全局最大路径和 ans。ans = Math.max(ans, sum);// 【职责二】计算并返回对父节点的“单边”贡献。// 路径不能分叉，所以只能选择左或右中贡献更大的那一条。// Math.max(left, right) + node.val 表示从 node 向下的最大单边路径和。// 再次与 0 比较，如果这条最佳单边路径的和是负数，就“剪掉”它，向上贡献 0。return Math.max(Math.max(left, right) + node.val, 0);}
}
时空复杂度
时间复杂度：O(N)
- 遍历：该算法的核心是深度优先搜索（DFS），它以后序遍历的方式访问树中的每一个节点。
- 访问次数：每个节点都会被访问且仅被访问一次。
- 节点操作：在每个节点的访问过程中，执行的都是常数时间的算术运算和
Math.max操作。 - 综合分析：
- 算法由
N次 O(1) 的操作组成，其中N是树中的节点数。 - 因此，总的时间复杂度是 O(N)。
- 算法由
空间复杂度：O(H)
- 主要存储开销：该算法的空间开销主要来自于递归调用栈。
- 递归深度：调用栈的最大深度取决于树的高度
H。- 最坏情况：如果树退化成一个链表（Skewed Tree），树的高度
H等于节点数N。此时，空间复杂度为 O(N)。 - 平均/最好情况：如果树是平衡的（Balanced Tree），树的高度
H约等于log N。此时，空间复杂度为 O(log N)。
- 最坏情况：如果树退化成一个链表（Skewed Tree），树的高度
综合分析：
算法的额外辅助空间复杂度由递归栈的深度决定，因此可以统一表示为 O(H)，其中 H 是树的高度。