题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个二叉树，求其中任意一个祖先节点与其子节点的数值差值最大值。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        # 自底向上
        ans = 0
        def dfs(root: Optional[TreeNode]):
            if not root:
                return inf, -inf
            left_min, left_max = dfs(root.left)
            right_min, right_max = dfs(root.right)
            min_num = min(root.val, left_min, right_min)
            max_num = max(root.val, left_max, right_max)
            nonlocal ans
            ans = max(ans, max_num - root.val, root.val - min_num)
            return min_num, max_num
        dfs(root)
        return ans
    

        # 优化自顶向下
        ans = 0
        def dfs(root: Optional[TreeNode], min_ancient_val:int, max_ancient_val):
            if not root:
                nonlocal ans
                ans = max(ans, max_ancient_val - min_ancient_val)
                return 
            
            nxt_min_val = min(min_ancient_val, root.val)
            nxt_max_val = max(max_ancient_val, root.val)
            dfs(root.left, nxt_min_val, nxt_max_val)
            dfs(root.right, nxt_min_val, nxt_max_val)

        dfs(root, root.val, root.val)
        return ans

        # 普通自顶向下
        ans = 0
        def dfs(root: Optional[TreeNode], min_ancient_val:int, max_ancient_val):
            if not root:
                return 
            
            nonlocal ans
            cur = max(root.val - min_ancient_val, max_ancient_val - root.val)
            if cur > ans:
                ans = cur
            nxt_min_val = min(min_ancient_val, root.val)
            nxt_max_val = max(max_ancient_val, root.val)
            dfs(root.left, nxt_min_val, nxt_max_val)
            dfs(root.right, nxt_min_val, nxt_max_val)

        dfs(root, root.val, root.val)
        return ans