LeetCode题练习与总结：二叉树中的最大路径和--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

提示：

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

二、解题思路

使用递归的方式，后序遍历二叉树，对于每个节点，计算其左子树和右子树的最大路径和。
对于每个节点，其最大路径和可以是其左子树的最大路径和、右子树的最大路径和、或者节点值本身，取这三者的最大值。
同时，需要记录一个全局变量，用于保存遍历过程中的最大路径和。

三、具体代码

class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 计算左子树的最大路径和
        int leftGain = Math.max(maxGain(node.left), 0);
        // 计算右子树的最大路径和
        int rightGain = Math.max(maxGain(node.right), 0);

        // 计算当前节点的最大路径和，并更新全局最大路径和
        int priceNewPath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewPath);

        // 返回当前节点的最大路径和
        return node.val + Math.max(leftGain, rightGain);
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

对于二叉树中的每个节点，我们都会调用一次 maxGain 函数。
在 maxGain 函数中，我们对每个节点的左右子节点各调用一次 maxGain 函数。
因此，每个节点只会被访问一次，所以时间复杂度是 O(N)，其中 N 是二叉树中节点的数量。

2. 空间复杂度

空间复杂度主要取决于递归栈的深度，这通常由树的高度决定。
在最坏的情况下，树完全不平衡，每个节点都只有一个子节点，递归栈的深度将是 O(N)。
在最好的情况下，树是完全平衡的，递归栈的深度将是 O(logN)。
因此，空间复杂度在最坏情况下是 O(N)，在最好情况下是 O(logN)。

综上所述，该算法的时间复杂度是 O(N)，空间复杂度在最坏情况下是 O(N)，在最好情况下是 O(logN)。

五、总结知识点

递归：这是一种常用的算法设计技巧，用于解决分而治之的问题。在这个问题中，我们使用递归函数 maxGain 来计算每个节点的最大路径和。
后序遍历：递归函数 maxGain 以后序遍历的方式访问二叉树的每个节点，即先访问左子树，然后是右子树，最后是当前节点。
二叉树的结构：代码中使用了 TreeNode 类来表示二叉树的节点，每个节点包含一个整数值 val 和两个指向其左右子节点的指针 left 和 right。
路径和的计算：在递归函数中，我们计算每个节点的左子树和右子树的最大路径和，然后将它们与当前节点的值相加，得到经过当前节点的最大路径和。
全局变量的使用：maxSum 是一个全局变量，用于在递归过程中记录遍历到的最大路径和。
边界条件的处理：当递归函数遇到空节点时，返回0，这表示如果子树的最大路径和为负，则可以忽略该子树。
数学函数的应用：Math.max 函数用于在递归过程中选择最大的路径和。这是处理最大路径和问题时的一种常见技巧，因为路径和可能是由多个部分组成的，我们需要选择最大的那一个。