力扣第124题 二叉树中的最大路径和
前言
记录一下刷题历程 力扣第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
分析
我们通过深度优先搜索递归地遍历二叉树的每一个节点。然后计算子树贡献，每个节点通过递归计算其左子树和右子树的最大贡献值（忽略负贡献），这意味着路径不能包含负值的部分。然后每个节点返回它能为其父节点提供的最大单边路径和（要么来自左子树，要么来自右子树的贡献，或者不选择子树）。最后在每个节点处，计算以该节点为中心的路径和，并更新全局的最大路径和。
可以根据下图进一步理解
代码如下：
// 定义一个类 Solution，其中包含计算最大路径和的函数
class Solution {
public:
// 主函数，计算二叉树的最大路径和
int maxPathSum(TreeNode* root) {
// 初始化结果为根节点的值
int res = root->val;
// 调用 dfs 函数进行深度优先搜索
dfs(root, res);
// 返回最终计算出的最大路径和
return res;
}
// 深度优先搜索函数，用于递归遍历树并计算最大路径和
int dfs(TreeNode* root, int& res) {
// 如果当前节点为空，返回 0
if (!root) {
return 0;
}
// 递归计算左子树的最大贡献值，如果小于 0 则取 0（不考虑负贡献）
int lmax = max(0, dfs(root->left, res));
// 递归计算右子树的最大贡献值，如果小于 0 则取 0（不考虑负贡献）
int rmax = max(0, dfs(root->right, res));
// 更新全局最大路径和：比较当前最大值与经过当前节点的路径和
// 路径经过当前节点 root，并且左右子树的贡献值都包含在路径中
res = max(res, lmax + rmax + root->val);
// 返回以当前节点为起点的最大路径和，选取左右子树中贡献较大的那一条路径
return root->val + max(lmax, rmax);
}
};
解释注释
1.主函数 maxPathSum(TreeNode* root)：
（1）参数：
传入树的根节点 root。
（2）.变量 res：
用于存储全局最大路径和，初始值为根节点的值 root->val，因为至少包含根节点的值。
（3）调用 dfs 函数：
通过深度优先搜索遍历整棵树，并在过程中更新最大路径和。
（4）返回结果：
最终返回全局最大路径和 res。
2.深度优先搜索函数 dfs(TreeNode* root, int& res)：
（1）参数：
root：当前递归遍历的节点。
res：引用，记录全局的最大路径和。
（2）基线条件：
如果当前节点 root 为空，则返回 0，表示空节点对路径和没有贡献。
（3）左子树和右子树的贡献值：
对左子树 root->left 调用 dfs 计算左子树的最大贡献值 lmax，如果小于 0 则返回 0（不考虑负数贡献）。
对右子树 root->right 调用 dfs 计算右子树的最大贡献值 rmax，同样如果小于 0 则取 0。
（4）更新最大路径和：
经过当前节点 root 的路径和为 lmax + rmax + root->val，即左右子树的贡献值加上当前节点的值。
将当前路径和与全局最大路径和 res 比较，更新 res 为较大的值。
（5）返回值：
返回当前节点能给上一层递归带来的最大贡献，即当前节点的值 root->val 加上左右子树中的最大贡献值 max(lmax, rmax)。这是因为路径不能分叉，只能选左右子树中的一条。
时间复杂度
每个节点都被递归访问了一次，而且在每次访问时，执行的操作（计算左子树和右子树的最大贡献、更新结果等）都是常数时间操作。因此，整个算法的时间复杂度是 O(N)，即与树中的节点数成正比。
总结