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

---

题目

描述： 二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。 路径和是路径中各节点值的总和。 给你一个二叉树的根节点 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。

---

解题思路

核心方法

深度优先搜索（DFS）+ 全局变量维护最大值：

1. 定义路径和：对于每个节点，计算以该节点为根的子树中，从该节点出发向下的最大路径和（只能选择左或右子树中的一条路径）。
2. 更新全局最大路径和：在计算每个节点的向下最大路径和时，同时计算以该节点为顶点的路径和（左子树向下路径和 + 右子树向下路径和 + 当前节点值），并更新全局最大路径和。
3. 递归返回值：返回以当前节点为起点的向下最大路径和（若为负数则返回 0，因为负数路径对后续路径和无增益）。

算法步骤

1. 初始化全局变量：ans = Integer.MIN_VALUE，用于存储最大路径和。
2. 深度优先搜索：
   • 若当前节点为 null，返回 0。
   • 递归计算左子树和右子树的向下最大路径和（若为负则取 0）。
   • 计算以当前节点为顶点的路径和（左 + 右 + 当前节点值），并更新 ans。
   • 返回以当前节点为起点的向下最大路径和（左、右中的较大值 + 当前节点值，若为负则返回 0）。
3. 返回结果：递归结束后，返回 ans。

---

代码实现

DFS + 全局变量（Java）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    int ans = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    
    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        ans = Math.max(ans, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

---

总结

1. 该方法通过一次深度优先遍历，同时计算向下路径和与顶点路径和，时间效率高。
2. 全局变量 ans 用于维护最大路径和，避免了额外的空间开销。
3. 处理负数路径时，通过取 Math.max(dfs(...), 0) 确保只有增益路径被计入，提升了算法的鲁棒性。

---