一、文章标题
LeetCode 124. 二叉树中的最大路径和 - 后序DFS与分治DP详解

二、文章内容

1. 题目概述

• 题目描述：给定非空二叉树的根节点 root，路径被定义为一条从任意节点出发、到任意节点结束的序列，序列中相邻节点必须通过边相连，且每个节点至多出现一次。路径不必经过根节点。请返回所有可能路径中节点值之和的最大值。
• 原题链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/
• 难度等级：Hard
• 相关标签：二叉树、DFS、后序遍历、分治、动态规划

2. 文章目录

目录

1. 题目概述
2. 解题思路
3. 算法详解
   • 3.1 解法一：后序DFS + 全局最大值（单侧增益）
   • 3.2 解法二：分治二元组DP（maxDown, maxPath）
4. 解法对比
5. 最优解推荐

3. 解题思路

• 问题分析：
  • 输入：二叉树根节点 root（节点值可为负）。
  • 输出：整数，表示二叉树中所有路径和的最大值。
  • 路径：可从任意节点出发到任意节点结束，沿父子边走，不能重复节点；不要求经过根。
• 核心难点：
  • 节点值可能为负，若无处理会拉低路径和。
  • 对于经过某个节点的“最佳路径”，可以选择同时经过其左、右子树（左右分支在该节点处合并），但向上返回父节点时只能保留一条分支（否则会出现分叉，不是简单路径）。
  • 需要区分“向上可延伸的单侧贡献”和“在当前节点处闭合的整条路径和”。
• 解题方向：
  1. 后序DFS + 全局最大值：递归返回“从当前节点向上能提供的最大单侧增益”，在回溯处用“左单侧 + 右单侧 + 当前值”更新全局答案；单侧增益使用 max(0, ·) 对负值剪枝。
  2. 分治二元组DP：每个子树同时返回两类信息：maxDown（从根向下的最大单侧路径）与 maxPath（该子树内部的最大路径和），在父节点合并。

4. 算法详解

解法一：后序DFS + 全局最大值（单侧增益）

算法原理

• 定义 dfs(node) 返回“从 node 出发、向上能提供的最大单侧增益”。
• 记 left = max(0, dfs(node.left))，right = max(0, dfs(node.right))，负增益剪枝为 0。
• 以当前节点为“拐点”时，完整路径和为 node.val + left + right，用它更新全局最大值；向上只能返回 node.val + max(left, right)。
• 适用场景：题目原型与常见面试高频题，思路简洁、实现短小。

具体实现

• 步骤1：定义全局 maxSum，初始化为 Integer.MIN_VALUE。
• 步骤2：后序遍历：先求左右子树单侧增益，再更新全局，再返回单侧增益给父节点。
• 步骤3：根为空时返回 0（默认值，避免异常）。

复杂度分析

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

Java代码实现

// LeetCode 已提供 TreeNode 定义：
// 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 {
    // 全局变量，记录遍历过程中的最大路径和
    private int maxSum;

    /**
     * 解法一：后序DFS + 全局最大值（推荐）
     * 若 root 为空返回 0 作为默认值，避免抛出异常；在有效数据下不影响正确性。
     */
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0; // 默认返回值，正常用例不会为 null
        }
        maxSum = Integer.MIN_VALUE; // 初始化为最小值，确保能被更新
        dfs(root);
        return maxSum;
    }

    // 返回从 node 出发、可向父节点延伸的最大单侧增益
    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 through = node.val + leftGain + rightGain;
        if (through > maxSum) {
            maxSum = through; // 更新全局最大值
        }

        // 返回给父节点的单侧增益：只能选左右中较大的一侧继续向上
        return node.val + Math.max(leftGain, rightGain);
    }
}

解法二：分治二元组DP（maxDown, maxPath）

算法原理

• 为每个子树返回二元信息：
  • maxDown：以该子树根为起点，向下走到任意节点的最大单侧路径和（允许不选子树，用 0 与子树值比较来剪枝）。
  • maxPath：该子树内部的最大路径和（可能经过根，也可能完全在左/右子树内部）。
• 合并：
  • 当前节点的 maxDown = max(0, max(left.maxDown, right.maxDown)) + node.val；
  • 当前节点的 maxPath = max(left.maxPath, right.maxPath, node.val + max(0,left.maxDown) + max(0,right.maxDown)).
• 适用场景：语义更“DP化”，便于拓展与证明。

具体实现

• 步骤1：编写 helper 返回 int[]{maxDown, maxPath}。
• 步骤2：空节点返回 {0, Integer.MIN_VALUE}（空树内部路径不可用，用极小值占位）。
• 步骤3：根节点答案为 helper(root)[1]，根为空时返回 0 作为默认值。

复杂度分析

• 时间复杂度：O(n)，每个节点处理一次。
• 空间复杂度：O(h)，递归栈占用。

Java代码实现

class Solution {
    /**
     * 解法二：分治二元组DP
     * 返回结果的第二项为最大路径和；root 为空时返回 0 作为默认值。
     */
    public int maxPathSumDP(TreeNode root) {
        if (root == null) {
            return 0; // 默认返回值
        }
        int[] ans = helper(root);
        return ans[1];
    }

    // 返回 {maxDown, maxPath}
    private int[] helper(TreeNode node) {
        if (node == null) {
            return new int[]{0, Integer.MIN_VALUE};
        }
        int[] L = helper(node.left);
        int[] R = helper(node.right);

        // 单侧向下最大：允许不取子树（用 0 剪枝负增益）
        int maxDown = node.val + Math.max(0, Math.max(L[0], R[0]));
        // 经过当前节点的“闭合路径和”
        int through = node.val + Math.max(0, L[0]) + Math.max(0, R[0]);
        // 子树内部最大路径和：三者取最大
        int maxPath = Math.max(Math.max(L[1], R[1]), through);

        return new int[]{maxDown, maxPath};
    }
}

5. 解法对比与总结

最优解推荐：基于时间、空间、可读性综合考虑，推荐“后序DFS + 全局最大值”方案；在保持 O(n) 时间、O(h) 空间的同时，代码最短、思路清晰，适合绝大多数场景。

三、文章标签

算法,二叉树,LeetCode,困难,DFS,分治,动态规划

四、文章简述

困难二叉树路径优化题。核心用后序DFS计算单侧最大增益并以“穿过当前”的两侧之和更新全局最大值，配合max(0,·)剪枝负增益；再给出分治二元组DP等价实现。含完整Java注释与复杂度分析，适合面试与刷题进阶。

转载自CSDN-专业IT技术社区

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/m0_52114506/article/details/152050413