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函数用于在递归过程中选择最大的路径和。这是处理最大路径和问题时的一种常见技巧，因为路径和可能是由多个部分组成的，我们需要选择最大的那一个。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。