二叉树中的最大路径和

题目

二叉树中的最大路径和

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

二叉树遍历,递归算法,动态规划思想,边界条件处理

快速回答

解决二叉树最大路径和问题的核心要点：

• 使用后序遍历递归计算每个节点的贡献值
• 节点贡献值 = 节点值 + max(左子树贡献, 右子树贡献, 0)
• 维护全局最大路径和：max(当前最大, 节点值 + 左贡献 + 右贡献)
• 时间复杂度：O(N)，空间复杂度：O(H)（H为树高）
• 关键代码结构：

  int maxPathSum(TreeNode root) {
      maxSum = Integer.MIN_VALUE;
      dfs(root);
      return maxSum;
  }

问题描述

给定一个非空二叉树，找到路径和的最大值。路径定义为树中任意节点到任意节点的序列，且至少包含一个节点。路径不可重复经过同一节点。

原理说明

该问题的难点在于路径可能跨越子树根节点。核心思路：

• 后序遍历：计算节点贡献值时需要先知道左右子树结果
• 贡献值计算：节点作为路径端点时的最大贡献值（非完整路径）
• 全局最大值更新：当节点作为路径转折点时，完整路径 = 左贡献 + 节点值 + 右贡献
• 负值处理：贡献值最小为0（表示放弃该子树）

代码示例（Java）

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;

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

        // 当前节点作为路径转折点时的完整路径和
        int priceNewPath = node.val + leftGain + rightGain;

        // 更新全局最大值
        maxSum = Math.max(maxSum, priceNewPath);

        // 返回当前节点作为端点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

最佳实践

• 初始化技巧：maxSum初始化为Integer.MIN_VALUE而非0，处理全负值树
• 剪枝优化：贡献值计算时与0比较，避免负贡献拖累路径和
• 递归边界：空节点返回0贡献值
• 空间优化：使用成员变量而非参数传递全局最大值

常见错误

• 未考虑负值：直接累加左右子树贡献导致结果偏小
• 路径重复计算：错误地将左右子树完整路径相加
• 忽略单节点情况：全负值树中最大路径和应是最大单节点值
• 修改原始树结构：不必要地修改节点值

扩展知识

• 相似问题：二叉树的直径（路径边数）、最长同值路径
• 非递归实现：使用后序遍历栈，需额外存储节点状态和贡献值
• 动态规划视角：节点贡献值即状态转移方程：
  dp[node] = val + max(dp[left], dp[right], 0)
• 树形DP：该问题是树形动态规划的经典案例，结合了最优子结构和状态转移