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

题目

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

给定二叉树的根节点 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解决方案，请移步力扣中等题解析