XingHuiSama の宝藏之地

1. 算法核心思想

本题要求寻找二叉树中节点值之和最大的路径。路径可以从任意节点开始，到任意节点结束，但必须连续且不能存在分叉。本解法采用后序遍历（自底向上）的递归策略，核心逻辑围绕“节点贡献值”与“全局最大值更新”展开：

最大单侧贡献值：对于树中的任意节点，当它作为子路径的一部分向父节点延伸时，只能选择其左子树或右子树中的一条分支（否则违背路径无分叉的规则）。
负值剪枝策略：由于节点值可能为负数，如果某条子分支提供的贡献值为负，将其接入当前路径只会拉低总和。因此，当子树的贡献值小于 0 时，应直接舍弃该分支，将其贡献值视为 0。
全局状态更新：在递归遍历每个节点时，将其视为当前路径的“最高点”，计算包含该节点及其左右非负子树的路径总和，并尝试更新全局的最大路径和记录。

2. 代码逻辑拆解

主函数 maxPathSum：初始化全局变量 maxsum 为系统最小整数 INT_MIN，以处理树中所有节点均为负数的极端情况。调用递归函数后，返回全局记录的最大值。
递归函数 func(TreeNode* node)：该函数的作用是计算并返回以 node 为起点的最大单侧路径贡献值。
- 终止条件：若当前节点为 NULL，返回贡献值 0。
- 计算子树贡献（含剪枝）：递归调用获取左、右子树的最大单侧贡献。通过 max(0, func(...)) 将负数贡献过滤为 0，意味着在逻辑上断开带来负收益的子树分支。
- 更新全局最大值：当前以 node 为路径最高点的最大路径和构成为：左侧非负贡献 + 右侧非负贡献 + 当前节点值。将其与 maxsum 比较并更新。
- 向父节点返回贡献：当前节点向上层提供的最大贡献，必须是在其左侧和右侧贡献中取较大者，再加上自身节点的值。即 max(maxleft, maxright) + node->val。

class Solution {
public:
    int maxsum = INT_MIN;
    
    int maxPathSum(TreeNode* root) {
        func(root);
        return maxsum;
    }
    
    int func(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }

        // 计算左右子树的单侧最大贡献，若为负数则按 0 处理（截断分支）
        int maxleft = max(0, func(node->left));
        int maxright = max(0, func(node->right));

        // 将当前节点视为路径最高点，计算完整路径和并尝试更新全局最值
        if (maxsum < maxleft + maxright + node->val) {
            maxsum = maxleft + maxright + node->val;
        }

        // 向父节点返回包含当前节点的最大单侧贡献
        return max(maxleft, maxright) + node->val;
    }
};

3. 复杂度分析

时间复杂度：**** $O(N)$

其中 $N$ 为二叉树的节点总数。后序遍历过程中，每个节点被且仅被访问一次，且节点内部的比较与加法操作时间复杂度均为 $O(1)$ 。因此总体时间复杂度为 $O(N)$ 。
空间复杂度：**** $O(H)$

其中 $H$ 为二叉树的高度。主要空间开销源于递归调用栈的深度。在最坏情况下（树退化为单链表），高度 $H = N$ ，空间复杂度为 $O(N)$ ；在最好情况下（树为完全二叉树），高度 $H = \log N$ ，空间复杂度为 $O(\log N)$ 。

‍