LeetCode124 二叉树中的最大路径和

  • 作者:zyh
  • 分类:LeetCode
  • 发表日期:2020-07-04 11:44:13
  • 阅读(414)
  • 评论(0)

给定一棵非空二叉树,从中找出最大路径和。

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

也就是说,这棵二叉树肯定是有节点的,最大路径和可能是多个节点的和也可能是一个节点。

实例一不难看出,最大路径和就是这三个节点的和。但是实例二可能就有点难理解

首先要计算各个节点的最大贡献值,空节点的最大贡献值等于0,非空节点的最大贡献值等于本身节点值加上子节点的值,如果有两个子节点,则选取最大的,叶子节点的最大贡献值等于其节点值。

这里我画了张图来理解理解

现在所有的贡献值都已经找完了,最大路径和此时是右子树的左节点15。然后开始回溯,向上找退回到20这个节点,此时price_newpath = left_gain + right_gain + node.val = 15 + 7 + 20 = 42 > 15,更新max_sum。

然后继续回溯,向上找到-10这个根节点,price_newpath = left_gain + right_gain + node.val = 9 + 35 -10 = 34 < 42,不更新max_sum。

可能会觉得35是从哪来的,前边也说过,最大贡献值等于本身节点值加上子节点的值,如果有两个子节点,则选取最大的,所以20这个节点的最大贡献值就等于15 + 20 = 30,根节点的最大贡献值就等于-10 + 35 = 25。

下面来看代码:

LeetCode124 二叉树中的最大路径和

提交评论

您尚未登录 :-( ,登录之后方可评论 登录 or 注册

评论列表

暂无评论