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

核心思想：后序遍历（DFS） 1. DFS 函数的作用是计算并返回以当前节点为终点的“单侧最大路径和”（只能继续走左子树或右子树），提供给父节点使用。 2. 在遍历过程中，同时计算以当前节点为“最高点”（可以同时包含左右子树）的“最大局部路径和”，并全局维护更新 ans。 3. 贪心策略：如果某个子树的单侧路径和为负数，把它加到路径里只会让总和变小。这时候我们将其置为 0，代表“不选这颗子树的路径”。

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;
    }
}
// @lc code=start
/**
 * Definition for a binary tree node.
 * public 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;

    /**
     * 核心思想：后序遍历（DFS）
     * 1. DFS 函数的作用是计算并返回以当前节点为终点的“单侧最大路径和”（只能继续走左子树或右子树），提供给父节点使用。
     * 2. 在遍历过程中，同时计算以当前节点为“最高点”（可以同时包含左右子树）的“最大局部路径和”，并全局维护更新 ans。
     * 3. 贪心策略：如果某个子树的单侧路径和为负数，把它加到路径里只会让总和变小。这时候我们将其置为 0，代表“不选这颗子树的路径”。
     */
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    // 返回当前子树下的最大路径和
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        left = left <= 0 ? 0 : left;
        right = right <= 0 ? 0 : right;
        ans = Math.max(ans, left + right + root.val);
        return Math.max(left, right) + root.val;
    }

}