leetcode124.二叉树中的最大路径和（Python3）

给定一个非空二叉树&＃xff0c;返回其最大路径和。

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

示例 1:

输入: [1,2,3]1/ \2 3输出: 6


示例 2:

输入: [-10,9,20,null,null,15,7]-10/ \9 20/ \15 7输出: 42&＃xff08;15&＃43;7&＃43;20&＃xff09;


方法&＃xff1a;递归

思路&＃xff1a;

我们首先考虑什么样的路径可以是最大路径&＃xff0c;根据题意&＃xff0c;只要是一个结点到另一结点即可。那么我们可以分成两种&＃xff1a;

• 单向路径&＃xff0c;即路径中所有的结点都不在同一层&＃xff0c;比如示例2中的-10→20→7。
• 双向路径&＃xff0c;路径中&＃xff0c;以根节点为最高层&＃xff0c;左右两个单路径向两边延伸&＃xff0c;比如示例二中的答案15←20→7。

我们考虑以每一个结点为根&＃xff0c;可以构成的最大单向路径和maxgain为多少&＃xff0c;叶节点的maxgain就为它本身的值&＃xff0c;其他结点的maxgain则为它自己的值与它左右结点中较大的maxgain之和。

如示例2中&＃xff0c;首先15和7的maxgain为本身&＃xff0c;然后20的maxgain为20&＃43;max(15,7)&＃61;35&＃xff0c;然后9的maxgain为本身&＃xff0c;-10的maxgain为-10&＃43;max(9,35)&＃61;25。

由上面的过程可以看出&＃xff0c;这是一个从下到上的计算过程&＃xff0c;因此用DFS递归可以完成计算。

我们再考虑答案与maxgain的关系&＃xff0c;如果以某个点node为路径的根&＃xff0c;那么双向路径的和为

node.val&＃43;maxgain(node.left)&＃43;maxgain(node,right)&＃xff1b;

单向路径为

node.val&＃43;maxgain(node.left)或node.val&＃43;maxgain(node.right)。

我们要找到这个结点为根的最大路径和&＃xff0c;那么就是上面三个式子的最大值&＃xff0c;而只有在左结点或右结点的maxgain<0&＃xff0c;答案才会是下面的式子&＃xff0c;所以我们首先判断左右结点的maxgain是不是小于0&＃xff0c;如果小于0&＃xff0c;置为0&＃xff0c;这样就都可以使用上面的式子来表示了。

由于计算路径和的时候&＃xff0c;所需的值都是这个节点以及下一层的值&＃xff0c;所以在遍历计算maxgain的同一个递归即可完成&＃xff0c;只要使用一个全局变量更新结果即可。

代码&＃xff1a;

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val &＃61; x
# self.left &＃61; None
# self.right &＃61; Noneclass Solution:def __init__(self):self.res &＃61; float(&＃39;-inf&＃39;)def maxPathSum(self, root: TreeNode) -> int:#该函数返回root为根的最大单项路径长度和&＃xff0c;同时更新答案self.resdef maxgain(root):if not root:return 0#获取root的左右结点的最大单路径和&＃xff0c;如果小于0则忽略 left &＃61; max(maxgain(root.left),0)right &＃61; max(maxgain(root.right),0)#以root为根&＃xff0c;加上左右两个最大路径即为以root为根的最大双向路径和&＃xff08;有一个为0时为单向路径&＃xff09;summ &＃61; root.val &＃43; left &＃43; right#更新最大值self.res &＃61; max(self.res,summ)return root.val &＃43; max(left,right)maxgain(root)#返回答案return self.res


结果&＃xff1a;