🔗 二叉树中的最大路径和

题目来源：124. 二叉树中的最大路径和 – 力扣（LeetCode）

---

📌 题目描述

路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。

• 同一个节点在一条路径中 至多出现一次；
• 路径 至少包含一个节点；
• 路径 不一定经过根节点。

路径和 是路径中各节点值的总和。

给定二叉树的根节点 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。

注意：路径不能“折返”两次（如 15 → 20 → 9），因为那样会导致 20 被访问两次，违反“每个节点至多出现一次”的规则。

---

⚠️ 提示

• 节点数目范围：[1, 3 × 10⁴]
• Node.val 范围：[-1000, 1000]
• 节点值可为负数，不能简单跳过负值子树，需动态判断是否“舍弃”子路径。

---

💡 解法：递归 + 贪心剪枝 —— O(n) 时间，O(h) 空间

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    // 返回：以当前节点为起点，向下延伸的最大单边路径和（可不选子树）
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子树的最大贡献值（负数则舍弃，用 0 代替）
        int leftGain = Math.max(0, dfs(node.left));
        int rightGain = Math.max(0, dfs(node.right));

        // 计算“经过当前节点”的完整路径和（左 ← 当前 → 右）
        int currentPathSum = node.val + leftGain + rightGain;

        // 更新全局最大路径和
        maxSum = Math.max(maxSum, currentPathSum);

        // 返回当前节点能向上提供的最大单边路径和（只能选一边）
        return node.val + Math.max(leftGain, rightGain);
    }
}

✅ 关键点：

• 路径只能“拐一次弯”：即形如 左子树 ← 根 → 右子树，不能继续向上再拐；
• 单边路径 vs 完整路径：
  • dfs 返回的是单边路径（用于父节点构建路径）；
  • 全局 maxSum 记录的是完整路径（可能包含左右子树）；
• 负贡献剪枝：若子树贡献为负，则用 0 代替（相当于不选该子树）。

---

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点被访问一次，每次操作 O(1)。
• 空间复杂度：O(h)
  • 递归栈深度为树高 h；
  • 最坏情况（链表）：O(n)；
  • 最好情况（平衡树）：O(log n)。

---

🧩 解题思路

为什么不能直接返回左右子树最大值之和？

因为路径不能分叉！
当向上传递时，父节点只能选择左或右其中一条路径继续延伸，不能同时选两边。

🌰 举例：
对于节点 20（示例2），其左右子树贡献分别为 15 和 7。

• 它能贡献给父节点 (-10) 的最大单边路径是 20 + max(15,7) = 35；
• 但它自己内部的完整路径可以是 15 + 20 + 7 = 42，这就是答案。

算法核心：两种路径角色

角色	说明	用途
完整路径	经过当前节点，可包含左右子树	用于更新全局最大值 maxSum
单边路径	从当前节点向下延伸，只能选左或右	用于返回给父节点，构建更长路径

为什么初始化 maxSum = Integer.MIN_VALUE？

因为节点值可能全为负数（如 [-3, -2, -1]），此时最大路径和就是最大的那个负数（-1），不能初始化为 0。