Leetcode124. 二叉树中的最大路径和

题目描述

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

img

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

img

1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

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

解题思路

这道题要求得出二叉树内的最大路径和。需要注意的有两点，一是不一定要求从根节点出发到达叶子结点，可以从任意结点出发，到达任意结点；二是结点的值可以为负。

这道题的难点在于如何处理从任意结点出发到任意借点结尾的路径和。写递归的时候，我们需要返回的只能是左子树加上根节点或者右子树加上根节点的最大值，而不能返回跨越根节点的从子树的某个结点出发到另一个结点结尾的路径和的值（因为这样会造成一个结点的重复访问）。我们的方法就是用innerSum来标记当前的最大值（可能跨越根节点），outputSum来标记左子树加上根节点或者右子树加上根节点的值。innerSum用来更新全局的最大路径和maxSum，outputSum用来返回。

具体的步骤如下：

  • 如果结点为空节点，返回为0；
  • 用leftSum和rightSum来标记左子树和右子树的最大路径和，它们的最小值是0。因为结点的值虽然可以为负数，但是我们可以不选择左子树的结点（选择路径和为负数的左子树，maxSum会变得更小），此时的路径和就为0。然后更新maxSum的值。
  • 计算相应的outputSum的值，并返回。

时间复杂度为：O(N)O(N)，NN是二叉树中的结点个数

空间复杂度为：O(N)O(N)，NN是二叉树中的结点个数

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int DFS(TreeNode* root,int &maxSum)
{
    if(root==nullptr)
    {
        return 0;
    }
    int leftSum=max(DFS(root->left,maxSum),0);
    int rightSum=max(DFS(root->right,maxSum),0);
    int innerSum=root->val+leftSum+rightSum;
    maxSum=innerSum>maxSum?innerSum:maxSum;
    int outputSum=max(leftSum,rightSum)+root->val;
    return outputSum;  
} 

int maxPathSum(TreeNode* root) 
{
   int maxSum=INT32_MIN;
   DFS(root,maxSum);
   return maxSum;
}