发表于 2024.04.05

• 可以使用层次遍历 + 维护根节点至当前节点路径的最大/最小值，然后每次遍历的时候都更新下最优解（选用 当前最优解 or 当前路径的最大值 - 最小值）。

  # 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
  
  from collections import deque
  
  
  class Solution:
      def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
          result = 0
          q = deque()
          q.append((root, root.val, root.val))  # max, min
          while q:
              node, max_val, min_val = q.popleft()
              result = max(max_val - min_val, result)
              if node.left:
                  lc = node.left
                  q.append((lc, max(lc.val, max_val), min(lc.val, min_val)))
              if node.right:
                  rc = node.right
                  q.append((rc, max(rc.val, max_val), min(rc.val, min_val)))
          return result

• LC 题目链接