1026. 节点与其祖先之间的最大差值
题目
给定二叉树的根节点 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
解答
代码
等价于求出树中的最大值和最小值：
python
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
min_tree = root.val
max_tree = root.val
ans = 0
def dfs(node):
if node is None:
return
nonlocal min_tree
nonlocal max_tree
nonlocal ans
t1 = min_tree
t2 = max_tree
min_tree = min(min_tree, node.val)
max_tree = max(max_tree, node.val)
ans = max(ans, max_tree - min_tree)
dfs(node.left)
dfs(node.right)
min_tree = t1
max_tree = t2
dfs(root)
return ans不用恢复现场的做法，把 min, max 当作 形参 传入递归函数：
python
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(node: Optional[TreeNode], mn: int, mx: int) -> None:
if node is None:
return
mn = min(mn, node.val)
mx = max(mx, node.val)
nonlocal ans
ans = max(ans, node.val - mn, mx - node.val)
dfs(node.left, mn, mx)
dfs(node.right, mn, mx)
dfs(root, root.val, root.val)
return ans