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

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

题目

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

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

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

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

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

解题思路

思路：递归

题目中所给出的路径概念是指【一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点】。

也就是说，要求出路径和，得计算节点能提供的最大贡献值。

对于节点能提供的贡献值，分为如下部分：

• 空节点提供的贡献值为 0；
• 对于非空节点提供的贡献值，等于当前节点的值与其子节点中提供最大贡献值的和。

现在以示例 1 来分析说明下：

输入: [1,2,3]

       1
      / \
     2   3

在这里叶子节点 2,3，能提供的贡献值就是 2， 3。

而叶子节点 1，能够提供的贡献值为 1+2 或 1+3。

那我们假设：如果节点 1 前面还有父节点，那么这里可能的路径就会变成：

• 2 + 1 + 3
• 2 + 1 + 1 的父节点
• 3 + 1 + 1 的父节点

其中第一种情况，就是求节点的最大路径和。这里节点的最大路径和取决于该节点与其左右子节点的最大贡献值之和。当然，在这里，如果子节点的贡献值为负，则选择不纳入。因为负数的贡献值添加进来反而会让结果变小。

对于第二种和第三种情况来说，这里就是递归求得左右子节点的贡献值，从中取更优的方案。

这里最主要的就是维护一个存储最大路径和的变量 max_path_sum，递归的过程中维护更新这个值，从而求得最大值。

具体的代码实现如下。

代码实现

# 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.max_path_sum = float('-inf')

    def maxPathSum(self, root: TreeNode) -> int:
        def max_contr(node):
            # 递归求节点最大贡献值
            # 同时维护经过节点的最大路径和
            # 空节点的贡献值为 0
            if not node:
                return 0

            # 递归计算左子节点的贡献值，
            left = max(0, max_contr(node.left))
            # 递归计算右子节点的贡献值
            right = max(0, max_contr(node.right))

            # 经过当前节点的最大路径和
            self.max_path_sum = max(self.max_path_sum, left + node.val + right)

            # 当前节点的贡献值，取左右子节点中的更优方案
            node_contr = node.val + max(0, max(left, right))
            # 这里返回的贡献值是给当前节点的上游节点
            return node_contr

        max_contr(root)
        return self.max_path_sum

实现结果

总结

• 从题目中得到的信息可以知道，要求最大路径和，需要求得节点能够提供的贡献值。
• 对于节点而言，提供的贡献值分为两部分：
  • 空节点的贡献值为 0；
  • 对于非空节点而言，当前节点能提供的贡献值为当前节点的值与其子节点中能提供的最大贡献值之和
• 对于非空节点而言，我们需要递归的方法求得每个节点的贡献值。同时，需要维护最大路径和，在这里，该节点的路径和取决于当前节点的值与其左右子节点的最大贡献值。
• 这里需要注意：当贡献值为负时，不计入节点的最大路径和。