题目124:二叉树中的最大路径和

题目描述

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

解题技巧

• 方法一:递归

首先,考虑实现一个简化的函数maxGain(node),该函数计算二叉树中的一个节点的最大贡献值,具体而言,就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径,使得该路径上的节点值之和最大。

具体而言,该函数的计算如下。

空节点的最大贡献值等于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,即可得到每个节点的最大贡献值。

根据函数maxGain得到每个节点的最大贡献值之后,如何得到二叉树的最大路径和?对于二叉树中的一个节点,该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值,如果子节点的最大贡献值为正,则计入该节点的最大路径和,否则不计入该节点的最大路径和。维护一个全局变量maxSum存储最大路径和，在递归过程中更新maxSum的值,最后得到的maxSum的值即为二叉树中的最大路径和。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class 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)
            rightGain = max(maxGain(node.right), 0)

            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain

            # 更新答案
            self.maxSum = max(self.maxSum, priceNewpath)

            # 返回节点的最大贡献值
            return node.val + max(leftGain, rightGain)

        maxGain(root)
        return self.maxSum

复杂度分析

时间复杂度:O(N),其中N是二叉树中的节点个数。对每个节点访问不超过2次。

空间复杂度:O(N),其中N是二叉树中的节点个数。空间复杂度主要取决于递归调用层数,最大层数等于二叉树的高度,最坏情况下,二叉树的高度等于二叉树中的节点个数。