124. 二叉树中的最大路径和

解题思路：递归 + 后序遍历（DFS）

这是一个典型的树形动态规划问题。关键在于理解：

路径可以拐弯（如左子树 → 根 → 右子树），但不能分叉（一旦向上就不能再同时走左右）。
对于每个节点，我们需要知道：
1. 以该节点为起点，向下的最大路径和（用于返回给父节点）
2. 以该节点为“最高点”（拐点）的路径最大和（用于更新全局答案）

定义递归函数：

int dfs(TreeNode node)

返回值：从当前节点向下延伸（可选择左或右或都不选）的最大路径和
在递归过程中，同时计算以当前节点为顶点的完整路径和，并更新全局最大值。

关键逻辑：

对于当前节点 node：
- 递归获取左右子树的“向下最大路径和”：leftMax, rightMax
- 剪枝：如果子树贡献为负，不如不选（用 Math.max(0, ...)）
- 当前节点作为路径顶点的总和为：
  node.val + leftMax + rightMax
- 更新全局最大路径和 maxSum
- 返回给父节点的值是：
  node.val + Math.max(leftMax, rightMax)
  （因为路径不能分叉，只能选一边向上）

Java 实现

class Solution {
    private int maxSum = Integer.MIN_VALUE;

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

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

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

        // 当前节点作为路径“最高点”的路径和
        int currentPathSum = node.val + leftMax + rightMax;

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

        // 返回给父节点的最大贡献（只能选一边）
        return node.val + Math.max(leftMax, rightMax);
    }
}

算法说明

为什么用 Math.max(0, ...)？
如果子树的最大路径和为负，那么不走该子树反而能得到更大的和（相当于只取当前节点）。
为什么返回 node.val + max(left, right)？
因为路径不能分叉，当这个节点要作为父节点路径的一部分时，只能选择左或右其中一条向下的路径。
为什么在递归中更新 maxSum？
因为最大路径可能出现在任意子树中，不一定经过根节点。

复杂度分析

时间复杂度：O(n)
每个节点访问一次。
空间复杂度：O(h)
递归栈深度，h 为树的高度（最坏 O(n)，平均 O(log n)）

边界情况处理

所有节点为负数 → 返回最大的那个负数（题目保证至少一个节点）
单节点树 → 返回该节点值
链状树（退化为链表）→ 正确处理单向路径