节点与其祖先之间的最大差值

🎯 问题描述（来源于LeetCode）

描述：
给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

说明：

  • 节点 A 是 B 的祖先，意味着 A 在从根节点到 B 的路径上。

  • 题目本质是求：在任意一条从根到叶子的路径上，最大值与最小值的差的最大值。

  • 示例：

    • 示例 1：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      输入：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 得出。

💻 解题思路

思路：DFS 深度优先搜索（状态传递）

代码实现

from typing import Optional

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        
        def dfs(node, min_val, max_val):
            if not node:
                # 到达空节点时，返回当前路径的最大差值
                nonlocal ans
                ans = max(ans, max_val - min_val)
                return
            
            # 更新当前路径上的最小值和最大值
            min_val = min(node.val, min_val)
            max_val = max(node.val, max_val)
            
            # 继续向左右子树遍历
            dfs(node.left, min_val, max_val)
            dfs(node.right, min_val, max_val)
        
        # 直接用根节点的值初始化最大值和最小值
        dfs(root, root.val, root.val)
        return ans

📊 性能分析

  • 时间复杂度：O(n)O(n)。其中 nn 为二叉树的节点数，每个节点只会被访问一次。
  • 空间复杂度：O(h)O(h)。其中 hh 为二叉树的高度，主要为递归调用栈的空间开销。

💡 思考

这道题的核心在于**“路径极值的动态维护”**。

  1. 对于任意一条从根到叶子的路径，节点与其祖先的最大差值，一定等于该路径上的最大值减去最小值。
  2. 我们不需要存储路径上所有的祖先节点，只需要在 DFS 向下遍历时，实时维护当前路径的 min_val 和 max_val。
  3. 当到达叶子节点（或空节点）时，计算当前路径的 max_val - min_val，并更新全局的最大差值。