1. 题目解析与核心思路
LeetCode 124题"二叉树中的最大路径和"是一个经典的树形动态规划问题。题目要求我们在一棵二叉树中寻找一条路径，使得路径上所有节点值的和最大。这里的路径定义为任意节点序列，序列中每对相邻节点之间都存在一条边，且同一个节点在路径序列中至多出现一次。
1.1 问题重述
给定一棵二叉树的根节点root，返回其最大路径和。路径不需要从根节点开始，也不需要在叶子节点结束，但必须保证路径是连续的。例如：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是15 → 20 → 7，路径和为15+20+7=421.2 关键观察点
解决这个问题的关键在于理解路径的构成方式。对于任意一个节点，经过它的最大路径和可能有以下三种情况：
- 只包含该节点本身
- 该节点加上左子树的某条路径
- 该节点加上右子树的某条路径
- 该节点加上左右子树的路径（形成"拐弯"路径）
2. 树形DP解法详解
2.1 递归定义
我们定义一个递归函数maxGain(node)，它返回以node为起点的向下延伸的最大路径和（即不拐弯）。同时，在递归过程中我们会计算经过node的最大路径和（可能拐弯），并更新全局最大值。
class Solution { public: int maxPathSum(TreeNode* root) { int maxSum = INT_MIN; maxGain(root, maxSum); return maxSum; } private: int maxGain(TreeNode* node, int& maxSum) { if (!node) return 0; // 递归计算左右子树的最大贡献值 int leftGain = max(maxGain(node->left, maxSum), 0); int rightGain = max(maxGain(node->right, maxSum), 0); // 计算经过当前节点的最大路径和（可能拐弯） int priceNewPath = node->val + leftGain + rightGain; // 更新全局最大值 maxSum = max(maxSum, priceNewPath); // 返回当前节点的最大贡献值（不拐弯） return node->val + max(leftGain, rightGain); } };2.2 时间复杂度分析
这个解法采用后序遍历的方式访问每个节点恰好一次，因此时间复杂度是O(N)，其中N是二叉树中的节点数量。空间复杂度取决于递归栈的深度，最坏情况下（树退化为链表）为O(N)。
3. 实现细节与边界处理
3.1 初始值设置
全局最大值maxSum初始化为INT_MIN，这样可以正确处理所有节点值都为负数的情况。例如树中所有节点都是-1，那么最大路径和应该是-1（单个节点）。
3.2 负贡献处理
在计算左右子树的贡献时，我们使用max(..., 0)来忽略负贡献。这意味着如果某子树的贡献为负，我们宁愿不选择它。
3.3 空节点处理
当节点为nullptr时，maxGain返回0，表示空子树没有贡献。
4. 常见错误与调试技巧
4.1 典型错误模式
- 忘记处理负值情况，导致计算结果偏大
- 混淆了"节点最大贡献值"和"经过该节点的最大路径和"两个概念
- 没有正确初始化全局最大值，导致全负数情况出错
4.2 调试建议
对于树类问题，建议构造以下测试用例：
- 单节点树
- 全负数树
- 完全二叉树
- 退化为链表的树
- 常规的平衡树
例如：
void test() { Solution sol; // 单节点 TreeNode* t1 = new TreeNode(5); assert(sol.maxPathSum(t1) == 5); // 全负数 TreeNode* t2 = new TreeNode(-3); t2->left = new TreeNode(-5); t2->right = new TreeNode(-1); assert(sol.maxPathSum(t2) == -1); // 常规案例 TreeNode* t3 = new TreeNode(-10); t3->left = new TreeNode(9); t3->right = new TreeNode(20); t3->right->left = new TreeNode(15); t3->right->right = new TreeNode(7); assert(sol.maxPathSum(t3) == 42); }5. 算法优化与变种思考
5.1 非递归实现
虽然递归实现简洁，但我们可以用后序迭代遍历来实现非递归版本。需要使用栈来模拟递归过程，并额外维护每个节点的状态（是否已处理左右子树）。
5.2 路径记录
如果需要输出具体路径而不仅仅是和，我们可以修改算法，在递归过程中同时记录路径节点。这需要维护更多的状态信息，但基本思路不变。
5.3 多叉树扩展
这个算法可以推广到多叉树情况。对于每个节点，我们需要考虑所有子树的贡献，选择最大的几个（具体数量取决于路径定义）来组合。
6. 同类题目推荐
- LeetCode 543 - 二叉树的直径
- LeetCode 687 - 最长同值路径
- LeetCode 337 - 打家劫舍 III
- LeetCode 1372 - 二叉树中的最长交错路径
- LeetCode 1026 - 节点与其祖先之间的最大差值
这些题目都采用了类似的树形DP思路，通过后序遍历在递归过程中维护和更新全局状态。掌握这个模式可以解决一大类二叉树路径问题。
