# LeetCode: 1026. 节点与其祖先之间的最大差值¶

## 1、题目描述¶

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 AB 的祖先）

|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3

• 树中的节点数在 2 到 5000 之间。
• 每个节点的值介于 0 到 100000 之间。

## 2、解题思路¶

• 递归法
• 从下级向上传递3个值，分别是

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
res = 0

def dfs(node: TreeNode):
if not node.left and not node.right:
return  0, node.val, node.val

if not node.left:
rm, r1, r2 = dfs(node.right)
cur = max([abs(node.val - x) for x in [r1, r2]] + [rm])
temp = [r1, r2, node.val]
return cur, max(temp), min(temp)
elif not node.right:
lm, l1, l2 = dfs(node.left)
cur = max([abs(node.val - x) for x in [l1, l2]] + [lm])
temp = [l1, l2, node.val]
return cur, max(temp), min(temp)
else:

lm, l1, l2 = dfs(node.left)
rm, r1, r2 = dfs(node.right)
cur = max([abs(node.val - x) for x in [l1, l2, r1, r2]] + [lm, rm])
temp = [l1, l2, r1, r2, node.val]
return cur, max(temp), min(temp)

res, _, _ = dfs(root)
return res