给定一棵非空二叉树,从中找出最大路径和。
路径被定义为一条从树种任意节点出发,到达任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
也就是说,这棵二叉树肯定是有节点的,最大路径和可能是多个节点的和也可能是一个节点。
实例一不难看出,最大路径和就是这三个节点的和。但是实例二可能就有点难理解
首先要计算各个节点的最大贡献值,空节点的最大贡献值等于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。
下面来看代码:
提交评论
您尚未登录 :-( ,登录之后方可评论 登录 or 注册