LeetCode算法学习：二叉树中的最大路径和（解题思路过程）

LeetCode算法学习：二叉树中的最大路径和（解题思路过程）

引用

CSDN

1.

https://blog.csdn.net/qq_40805720/article/details/143236835

本文将详细介绍LeetCode中一个关于二叉树最大路径和的算法题目。通过Java代码实现解题思路，并通过具体示例帮助读者理解算法的执行过程。

题目描述

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

提示：

• 树中节点数目范围是 [1, 3 * 10^4]
• -1000 <= Node.val <= 1000

解题思路详解（Java实现）

1. 定义全局变量：用来存储最大路径和的结果，初始化为最小值（例如Integer.MIN_VALUE），因为节点值可能是负数。
2. 设计递归函数：对于每一个节点，我们希望计算以该节点为起点的最大路径和，即从该节点向下延伸的路径和。注意，这条路径只能向一个方向延伸（左或右），不能同时向左右两边延伸，因为这样就不符合题目中“路径”的定义了。
3. 计算路径和：对于每个节点，计算其左子树和右子树的最大贡献值（如果为负，则贡献值为0）。然后更新全局变量，即以当前节点为最高点的路径和是否大于之前记录的最大路径和。
4. 返回值：递归函数需要返回以当前节点为起点的最大路径和给父节点使用，这里只能返回左子树或右子树中的较大值加上当前节点的值，因为路径不能分叉。

Java源代码：

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }
    private int helper(TreeNode node) {
        if (node == null) return 0;
        // 计算左右子树的最大贡献值，小于0则不计入
        int leftGain = Math.max(0, helper(node.left));
        int rightGain = Math.max(0, helper(node.right));
        // 更新最大路径和，当前节点作为最高点
        int priceNewpath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回当前节点的最大贡献值给父节点
        return node.val + Math.max(leftGain, rightGain);
    }
}

代码解析

• maxSum：用于保存整个树中的最大路径和。
• helper()方法是一个递归方法，它计算并返回以当前节点为起点的最大路径和。
• 在每次递归调用中，我们首先检查节点是否为空，如果为空则返回0。
• 接着计算左右子树的最大贡献值，这里使用Math.max(0, helper(...))确保负值不会被计入。
• 然后计算以当前节点为最高点的路径和，并与当前已知的最大路径和进行比较，更新maxSum。
• 最后返回以当前节点为起点的最大路径和，注意只能选一边（左或右），所以用Math.max(leftGain, rightGain)加上当前节点的值。

这种方法确保了每个节点只被访问一次，因此时间复杂度为O(n)，其中n是树中节点的数量。空间复杂度取决于递归栈的深度，最坏情况下为O(n)。

提供一些图形化的例子来帮助理解。我们先从一个简单的例子开始，然后再看一个稍微复杂一点的例子。

示例 1: 简单的二叉树

假设我们有以下二叉树：

    1
   / \
  2   3

解析步骤：

1. 初始化全局变量：

• maxSum = Integer.MIN_VALUE

2. 递归遍历：

• 从根节点1开始调用helper(1)。
• 计算左子树的最大贡献值leftGain：
• 调用helper(2)，返回值为2（因为没有子节点，直接返回节点值）。
• 计算右子树的最大贡献值rightGain：
• 调用helper(3)，返回值为3（因为没有子节点，直接返回节点值）。
• 计算以当前节点1为最高点的路径和：
• priceNewpath = 1 + 2 + 3 = 6
• 更新maxSum：
• maxSum = max(maxSum, 6) = 6
• 返回以当前节点1为起点的最大路径和：
• return 1 + max(2, 3) = 4

3. 最终结果：

• maxSum = 6

示例 2: 更复杂的二叉树

假设我们有以下二叉树：

    -10
    /  \
   9   20
      /  \
    15   7

解析步骤：

1. 初始化全局变量：

• maxSum = Integer.MIN_VALUE

2. 递归遍历：

• 从根节点-10开始调用helper(-10)。
• 计算左子树的最大贡献值leftGain：
• 调用helper(9)，返回值为9（因为没有子节点，直接返回节点值）。
• 计算右子树的最大贡献值rightGain：
• 调用helper(20)：
• 计算左子树的最大贡献值leftGain：
• 调用helper(15)，返回值为15（因为没有子节点，直接返回节点值）。
• 计算右子树的最大贡献值rightGain：
• 调用helper(7)，返回值为7（因为没有子节点，直接返回节点值）。
• 计算以当前节点20为最高点的路径和：
• priceNewpath = 20 + 15 + 7 = 42
• 更新maxSum：
• maxSum = max(maxSum, 42) = 42
• 返回以当前节点20为起点的最大路径和：
• return 20 + max(15, 7) = 35
• 计算以当前节点-10为最高点的路径和：
• priceNewpath = -10 + 9 + 35 = 34
• 更新maxSum：
• maxSum = max(maxSum, 34) = 42
• 返回以当前节点-10为起点的最大路径和：
• return -10 + max(9, 35) = 25

3. 最终结果：

• maxSum = 42