题目描述

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

路径和是路径中各节点值得总和。
给你一个二叉树的根结点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\ast 10^4]$
• $-1000\le Node.val\le 1000$

解题过程

本题采用递归的思想解决。首先，实现定义一个函数maxGain，该函数的作用是计算二叉树中某个节点的最大贡献值，即在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。过程如下：

• 如果节点为空，则贡献值为0；
• 如果节点非空，则贡献值等于该节点值与其子节点中的最大贡献值之和（对于叶节点，最大贡献值为其本身的值）。

例如，考虑如下二叉树：

   -10/ \9  20/  \15   7

其中，叶节点9，15，7的最大贡献值分别为9，15，7。叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。例如，节点20的最大贡献值为20+max(15,7)=35，节点-10的最大贡献值为-10+max(9,35) = 25。

上述过程为递归的过程，因此，对根节点调用maxGain，即可对每个节点的最大贡献值进行计算。

得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和呢？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值。

• 如果子节点的最大贡献值为正，则计入该节点的最大路径和；
• 如果为负或0，则不计入该节点的最大路径和。

维护一个全局变量maxSum，存储最大路径和，在递归的过程中更新maxSum的值，最后得到maxSum的值即为二叉树中的最大路径和。

代码展示

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName  :MaxPathSum.py
# @Time      :2022/1/24 19:39
# @Author    :PangXZ
from typing import Optional# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self.maxSum = float('-inf')def maxPathSum(self, root: TreeNode) -> int:def maxGain(node):if not node:return 0# 递归计算左右子节点的最大贡献值# 只有在最大贡献值大于0时，才会选取对应子节点leftGain = max(maxGain(node.left), 0)    # 如果子树路径为负,则应当置为0，表示最大路径不包含该子树rightGain = max(maxGain(node.right), 0)# 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值priceNewpath = node.val + leftGain + rightGain# 更新答案，判断在该节点包含左右子树的路径和是否大于当前最大路径和self.maxSum = max(self.maxSum, priceNewpath)# 返回节点的最大贡献值return node.val + max(leftGain, rightGain)"""对于任意一个节点，如果最大和路径包含该节点，则只有两种情况：1. 其左右子树所构成的路径值较大的那个加上该节点的值后向父节点回溯构成最大路径2. 左右子树都在最大路径中，加上该节点的值构成了最终的最大路径"""maxGain(root)return self.maxSum

复杂度分析

• 时间复杂度：$O(N)$，其中N是二叉树中的节点个数。对每个结点访问都不超过2次；
• 空间复杂度：$O(N)$，空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的结点个数。

补充：Java代码

class Solution {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode node) {if (node == null) {return 0;}// 递归计算左右子节点的最大贡献值// 只有在最大贡献值大于 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);}
}