算法思想

这道题要求在一棵二叉树中找到路径和最大的路径。路径可以从树中任意一个节点开始，到任意一个节点结束，但路径上的节点必须是连续的。

算法使用递归的方式来遍历树中的每个节点，并在遍历过程中计算包含当前节点的最大路径和。具体步骤如下：

1. 递归辅助函数 (calculatePathSum)：

   • 这个函数用于计算以当前节点为起点的最大路径和。
   • 它通过递归分别计算左右子树的最大路径和，然后加上当前节点的值来得到当前路径的和。

2. 路径和的计算：

   • leftMax 和 rightMax 分别表示左子树和右子树的最大路径和，但如果子树路径和为负数，则忽略该子树路径，即设为 0，因为负数会降低总路径和。
   • currentMaxPathSum 代表了经过当前节点的路径和，包含左子树路径、当前节点值、右子树路径之和。

3. 全局最大路径和的更新：

   • 每当计算出一个 currentMaxPathSum，就将其与当前的全局最大路径和 maxSum 比较，以确保 maxSum 始终保存最大值。
   • 这样就能保证即使最优路径不经过根节点，也能记录全局最大路径和。

4. 返回值：

   • 函数返回当前节点值加上左右子树中较大的那个路径和，这样在递归向上返回时，可以确保每个节点返回的路径是包含它自身和一边子树的最大路径和。

复杂度分析

• 时间复杂度：(O(n))，其中 (n) 是树中的节点数，因为每个节点只访问一次。
• 空间复杂度：(O(h))，其中 (h) 是树的高度，这是递归调用栈的最大深度。

代码的运行流程示例

假设输入的树结构如下：

    1/ \2   3

• 从根节点 1 开始，递归计算其左右子树的最大路径和。
• 对于节点 2 和节点 3，它们的左右子树均为 null，因此它们的左右路径和为 0。
• 计算出节点 2 的最大路径和为 2，节点 3 的最大路径和为 3。
• 根节点 1 的路径和为 1 + 2 + 3 = 6。
• 最终结果是 6。

class Solution {private int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {calculateSum(root);return maxSum;}private int calculateSum(TreeNode root) {if(root == null) return 0;int leftMax = Math.max(calculateSum(root.left), 0);int rightMax = Math.max(calculateSum(root.right), 0);int currentmaxSum = root.val + leftMax + rightMax;maxSum = Math.max(currentmaxSum, maxSum);return root.val + Math.max(leftMax, rightMax);}
}

为什么 calculateSum 返回的不是node.val + leftMax + rightMax;?

这行代码的设计是因为我们要分清两种不同的情况：

1. 更新全局最大路径和：

   • 我们在每个节点处计算经过该节点的完整路径和，这条路径是包含了左子树、当前节点和右子树的路径和，即 node.val + leftMax + rightMax。这就是我们在 maxSum = Math.max(maxSum, currentMaxPathSum); 这一步中更新的内容。
   • 这个路径和会用于更新全局最大路径和 maxSum，因为这可能是当前遇到的最大路径。

2. 返回值的意义：

   • 在递归中，返回值代表以当前节点为起点向上递归时的“可选最大路径和”。
   • 注意，递归返回时不能同时选择左右子树的路径，因为递归往上走只能选择一条单一路径，而不是一条完整的左-当前-右的路径。
   • 因此，返回 node.val + Math.max(leftMax, rightMax);，表示从当前节点向上递归时，所能带回的最大路径和只能选择左子树或右子树中的较大者，来形成一条单向的路径。

总结

如果直接返回 node.val + leftMax + rightMax，那么递归上层的节点就会以包含当前节点左右子树路径的方式继续扩展路径，造成逻辑上的错误，因为每条路径必须是从上往下的一条单路径。

所以：

• 全局最大路径和：用 node.val + leftMax + rightMax 来更新，因为这条路径可以是左-当前-右的完整路径。
• 递归返回值：用 node.val + Math.max(leftMax, rightMax)，因为只能选择左右子树中的一个路径继续往上递归。