这题不能用回溯，必须用带状态传递的递归；因最大路径和依赖节点向上反馈的单向最大贡献值，回溯无法自然支持状态聚合与全局更新。
直接说结论：这题不能用回溯，必须用带状态传递的递归，且“路径和”与“节点贡献值”是两套值，混用必错。
为什么不能用回溯（backtracking）
回溯的本质是试探 + 撤销，适用于路径枚举类问题（比如找所有从根到叶的路径、路径总和等于 target 的路径）。但最大路径和不需要枚举所有路径，它依赖每个节点向上反馈的局部最优信息——即“我能向父节点提供多大贡献”。回溯无法自然携带这个“向上聚合”的状态，强行套用会导致重复计算或漏更新全局最大值。
常见错误现象：stack overflow（深度过深）、max_sum 始终不更新、返回值始终为负或为 0。
- 回溯函数通常无返回值（或只返回 bool），但本题需要每个节点返回
max_gain(node) - 回溯会反复 push/pop 路径节点，而本题只需一次遍历 + 两个变量：
left_gain和right_gain - LeetCode 官方题解和 Hot100 高频实现全部使用递归+引用/全局变量更新，无一例用 backtracking
max_gain(node) 返回什么、不返回什么
这个函数不是求“以 node 为端点的最大路径和”，而是求“从 node 向下延伸、最多只能走一条分支（左或右）所能获得的最大增益”。它服务于父节点构造跨子树路径，因此必须满足：只能选左或右其一，且负贡献要截断为 0。
关键参数差异：
-
max_gain(node->left)可能为负 → 实际参与计算时要max(0, ...) -
node->val + left_gain + right_gain是完整路径和（可跨左右），用于更新全局res -
node->val + max(left_gain, right_gain)是返回值（只能单向），供上层调用
示例（节点值为 20，左子树贡献 15，右子树贡献 7）：
lmr = 20 + 15 + 7 == 42 // 更新全局最大值 ret = 20 + max(15, 7) == 35 // 返回给父节点
C++ 实现中容易踩的三个坑
实际写的时候，这几个点几乎人人都卡过：
- 全局变量初始化错误：用
INT_MIN初始化res，而不是 0 或 -1 —— 因为节点值可能全为负，如[-3]，答案就是 -3 - 空节点返回值写成
return 0是对的，但有人误写return INT_MIN，导致max(0, ...)失效 - 更新
res的位置放错：必须在计算完left_gain和right_gain后立刻更新，不能等到 return 之后；否则漏掉以当前节点为顶点的路径
精简可靠的 C++ 片段：
int res = INT_MIN;
int max_gain(TreeNode* root) {
if (!root) return 0;
int left = max(max_gain(root->left), 0);
int right = max(max_gain(root->right), 0);
res = max(res, root->val + left + right); // 关键：这里更新！
return root->val + max(left, right);
}
递归深度与性能边界在哪
该算法时间复杂度是 O(n)，每个节点访问一次；空间复杂度是 O(h)，h 为树高，由递归栈决定。真正影响性能的不是逻辑，而是树的形态：
- 链状树（退化为链表）：h ≈ n，可能导致
stack overflow—— 此时需手动转迭代（用显式栈模拟），但 LeetCode 默认栈足够深（一般 > 1000 层） - 极端不平衡树：左子树极深、右子树为空，
max_gain仍只递归一次，无额外开销 - 注意：不要在递归中新建 vector 或 string 存路径 —— 这会把 O(h) 空间拉到 O(n·h)，直接超内存
最易被忽略的一点：所有子树贡献值都必须和 0 取 max，不是为了“美化结果”，而是语义要求——路径可以中途终止，不强制走到叶子。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
