1026. 结点与其祖先之间的最大差值(Python)

2021-05-27  本文已影响0人  玖月晴

难度:★★★☆☆
类型:树
方法:深度优先搜索

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。

(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)

示例 1:

输入:root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出:7
解释:
我们有大量的节点与其祖先的差值,其中一些如下:
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中,最大值 7 由 |8 - 1| = 7 得出。

示例 2:

输入:root = [1,null,2,null,0,3]
输出:3

提示:

树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 10^5

解答

树的问题一般用深度优先搜索解决。

一棵树,根节点有一个,叶子节点有很多,每个叶子节点都有一个到达根节点的直通路径,题目中所求的,实际上就是求所有路径中,结点差值最大的一个。结点差值定义为路径中最大值与最小值之差。

在定义深度优先搜索函数之前,我们有必要准备一些变量用来保存最终结果和中间结果。

self.max_diff作为全局变量,是最后的返回值,更新该变量的条件是,我们已经完成了从根节点到叶子节点的一条支路的遍历。

max_val和min_val:一条路径上的最大值和最小值,只有当遍历到达叶子节点时,这两个值才能算做真正的寻找到了,期间只能当做暂存器。还要注意的是,这两个值不能作为全局变量,原因是路径有很多条,每条路径都有各自的最大值和最小值。这两个暂存器需要在递归函数中作为参数传递,以此保证路径搜索过程中单条路径中这两个参数的连续性。

递归的深度优先搜索函数的设计,同其他递归函数一样,入口处给出跳出条件,也就是已经完成一条路径的探索,到达叶子节点时的状况,这时,我们的暂存器max_val和min_val中存储的就是整条路径的最大和最小值和,它们相减就是当前路径的结果,使用该结果更新全局结果self.max_diff。

其他情况下,需要根据当前节点的值更新暂存器max_val和min_val,并分别对左右子树进行搜索。

所有路径遍历完成,即可返回所有路径的最大差值self.max_diff。

class Solution:

    def maxAncestorDiff(self, root):

        self.max_diff = 0

        def dfs(node, max_val, min_val):
            if not node:
                self.max_diff = max(max_val - min_val, self.max_diff)
            else:
                max_val, min_val = max(max_val, node.val), min(min_val, node.val)
                dfs(node.left, max_val, min_val)
                dfs(node.right, max_val, min_val)

        dfs(root, -float("inf"), float("inf"))
        return self.max_diff

如有疑问或建议,欢迎评论区留言~

有关更多力扣中等题的python解决方案,请移步力扣中等题解析

上一篇下一篇

猜你喜欢

热点阅读