Hard 级：二叉树中的最大路径和
今天分析的这道题目，是LeetCode上 Hard 级别的一道题目，虽然代码行数只有 10 来行。
一 先来看看题目
给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1：
输入：[1,2,3]
1
/ \
2 3
输出：6
示例 2：
输入：[-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出：42
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
二 分析
这道题目的思路基本可以套用 最大子数组和 ，如果之前并不熟悉最大子数组和的动态规划解法，这道题可能就非常难，关于 最大子数组和，可以参考我昨天整理的完整分析，算是动态规划的入门篇：
最大子数组和，动规解法，可以看作一维的；二叉树子树和，可以看作二维的，思路具有一致性。
最大二叉子树和，也有一个包含当前节点的最大收益定义：current_sum，它被定义为：node.val + max( preOrder(node.left), preOrder(node.right) )，这是二维最大子树问题的关键决策方程，或者状态转移方程。
下面通过题目给出的二叉树为例，解释上面的决策方法：
待求解的二叉树：
自底向上(bottom-up)，分别求出每个节点的current_sum，对于叶节点，current_sum等于自身值，但是需要注意：如果current_sum小于0，直接丢弃此节点，认为贡献值为0，所以每个节点的current_sum都是不小于0的：
而节点20的 current_sum 等于：
节点 -10 的 current_sum 等于节点 20 和节点 9 最大值，加上 -10：
这样求解出每一个节点的 current_sum，这部分代码可以写为：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.best_sum = float('-inf')
def preOrder(node):
# 空节点返回 current_sum, 0
if not node:
return 0
# preOrder(node.left) < 0 ，丢弃左子树
current_sum_left = max(preOrder(node.left), 0)
# 同理， < 0，丢弃右子树
current_sum_right = max(preOrder(node.right), 0)
# 包括当前节点的最大累积和，编个名词，就说包括node节点的最大贡献值
current_sum = node.val + max(current_sum_left,current_sum_right)
return current_sum
preOrder(root)
return self.best_sum
接下来，如何找出最大路径和呢？
我们可以在上面自底向上递归的同时，寻找出每个节点对应的最大路径path_sum，对于node节点的path_sum，通过公式：path_sum = node.val + current_sum_left + current_sum_right 求出，如果current_sum_left 等于0，current_sum_right 等于0，则path_sum等于node.val:
同理，还有如下三种情况：
选择最大的path_sum，就得到最大二叉子树和
三 完整代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.best_sum = float('-inf')
def preOrder(node):
# 空节点返回 current_sum, 0
if not node:
return 0
# preOrder(node.left) < 0 ，丢弃左子树
current_sum_left = max(preOrder(node.left), 0)
# 同理， < 0，丢弃右子树
current_sum_right = max(preOrder(node.right), 0)
# 路径的意味就出来了，
# 可能4种情况：
# 1) 路径只有node节点
# 2)3) 仅有左子树、仅有右子树
# 4) 都有左、右子树
path_sum = node.val + current_sum_left + current_sum_right
# 选择最大的current_sum
self.best_sum = max(self.best_sum, path_sum)
# 包括当前节点的最大累积和，编个名词，就说包括node节点的最大贡献值
current_sum = node.val + max(current_sum_left,current_sum_right)
return current_sum
preOrder(root)
return self.best_sum
希望此文对大家有帮助！
算法的步骤，有时难以用文字和图片讲清楚，所以我会发布算法短视频到我的视频号：程序员zhenguo，欢迎各位读者一起关注学习。我的目标：讲清楚常用的算法和数据结构，结合图文和动画，真正提升程序的性能，帮助大家晋升为高逼格的程序员，帮助大家顺利进入大厂！！！
程序员zhenguo
我的视频号