电商网站设计是干什么的_商标转让费用_深圳网站优化公司哪家好_网络营销课程培训

题目描述：

给定一个非空二叉树，返回其最大路径和。路径的起点和终点可以是树中的任意节点。

示例：

示例 1:

输入：

     1/ \2   3

输出：6

示例 2:

输入：

     -10/    \9     20/  \15   7

输出：42

解题思路：

这道题的核心在于定义递归函数来计算从任意节点出发的最大路径和。我们可以通过深度优先遍历（DFS）来解决此问题。

1. 对于每个节点，我们需要计算：

   • 左子树的最大路径和。
   • 右子树的最大路径和。
   • 当前节点作为路径中的一部分时，最大路径和（即当前节点和它的子树的最大路径和）。

2. 我们的目标是：找出路径中包含当前节点、左子树和右子树的最大值。该最大值将更新全局的最大路径和。

3. 递归返回当前节点的最大路径和是：当前节点的值加上左右子树的最大路径和（如果是正数，否则为零），因为我们只能选择加上正的部分，避免路径和减少。

public class Solution {private int maxSum = Integer.MIN_VALUE;  // 存储全局最大路径和public int maxPathSum(TreeNode root) {// 调用递归函数，计算最大路径和maxGain(root);return maxSum;}// 递归函数计算当前节点的最大路径和private int maxGain(TreeNode node) {// 递归终止条件：如果当前节点为空，则返回0if (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);}// TreeNode定义public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}
}

解释：

1. maxGain函数：这是一个递归函数，它计算并返回以当前节点为根的最大路径和。

   • leftGain 和 rightGain 分别是从左子树和右子树获得的最大路径和。如果子树的路径和是负数，则我们不会选择这个子树，因此使用 Math.max(maxGain(node.left), 0) 来确保不选负路径。

2. priceNewPath：当前节点的路径和，等于节点值加上左右子树的最大路径和。

3. maxSum：在遍历过程中，更新全局的最大路径和。

4. 返回值：maxGain 函数返回当前节点作为路径的一部分时的最大路径和。该值用于父节点的递归计算。

时间复杂度：

• O(n)，其中 n 是二叉树中的节点数。因为我们遍历每个节点一次。

空间复杂度：

• O(h)，其中 h 是二叉树的高度。递归调用栈的深度取决于树的高度，最坏情况下是树的高度 h，如果是平衡树，空间复杂度是 O(log n)，如果是链状树，空间复杂度是 O(n)。