leetcode：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：问题性质分析

问题定义

1. 给定一棵二叉树，路径和定义为路径中所有节点值的总和。
2. 一条路径可以从任意节点开始，到任意节点结束，但每个节点在路径中只能出现一次。
3. 求出所有可能路径的最大路径和。

输入输出

• 输入：二叉树的根节点 root。
• 输出：一个整数，表示二叉树的最大路径和。

约束条件

• 树中节点数量范围为 [1, 3 * 10^4]。
• 每个节点的值范围为 [-1000, 1000]。

潜在边界条件

• 单节点树：例如 root = [1]。
• 节点值全为负数：例如 root = [-1, -2, -3]。
• 树的不平衡情况：例如左或右子树为空。

步骤 2：解题思路

算法设计：递归 + 分治

这道题可以用递归结合分治法解决，核心思想是动态规划 + 后序遍历。每个节点都可以有四种选择来计算路径和：

1. 仅包含自身。
2. 包含自身和左子树的最大贡献值。
3. 包含自身和右子树的最大贡献值。
4. 包含自身、左子树的最大贡献值和右子树的最大贡献值。

关键点：

• 我们需要维护一个全局变量来记录最大路径和。
• 使用后序遍历，从底向上计算每个节点的最大贡献值，并更新全局最大值。

步骤

1. 定义递归函数 maxGain(node)，返回当前节点的最大贡献值。
   • 若节点为空，返回 0。
   • 递归计算左子树和右子树的最大贡献值。如果贡献值为负数，则认为其为 0。
   • 计算当前节点作为路径根节点时的路径和，更新全局最大值。
   • 返回当前节点的最大贡献值。
2. 初始调用 maxGain(root)，返回全局最大值。

复杂度分析

• 时间复杂度：每个节点遍历一次，复杂度为 O(n)O(n)O(n)。
• 空间复杂度：递归栈的深度为树的高度，平均情况下为 O(log⁡n)O(\log n)O(logn)，最坏情况下（链式树）为 O(n)O(n)O(n)。

步骤 3：C++代码实现

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

代码注释

1. maxGain 递归函数计算当前节点的最大贡献值，同时更新全局最大路径和。
2. 当节点为空时，直接返回 0。
3. 对每个节点，计算包含该节点在内的最大路径和，并更新全局最大值。
4. 返回当前节点的最大贡献值，用于其父节点的路径计算。

步骤 4：算法优化与启发

优化方向

• 剪枝：当子树的值明显低于 0 时，提前停止递归计算。
• 动态规划迭代法：在树的特定情况下，可以将递归转化为栈模拟的迭代法，以避免过深的递归栈。

启发

• 分治与动态规划结合：此算法通过递归分治，逐步积累全局信息，展示了递归方法处理复杂问题的优势。
• 负值处理：问题引入了对负数的合理性判断，启发我们在处理复杂数据时应特别考虑边界值。

步骤 5：实际应用与场景分析

实际应用

• 电路分析：在电路中寻找最大功率路径。每个节点表示一个电子元件的功率贡献，每条边表示一条连通路径，目标是找到最大功率的路径。
• 交通网络优化：在交通路网中找到一条贡献最大的路径，路径上的节点和边表示交通量的贡献。

应用示例

场景：智能物流路径规划

• 问题：在仓库网络中，每个节点表示仓库，边表示配送线路，路径和表示配送效率。目标是找到一个路径，使得配送效率最大化。
• 实现：通过类似的递归算法，计算每条路径的效率，并更新全局最大值。
• 效果：提升物流效率，减少配送成本。