Leetcode # 1026. Maximum Difference Between Node and Ancestor

Problem

https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Solution

Time Complexity: O(len(tree))
Space Complexity: O(max_depth(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
    max_v = 0
    stack = [(root, root.val, root.val)] if root else []
    while stack:
      curr, max_a, min_a = stack.pop()
      # ... some process about target
      max_v = max(max_v, max_a - curr.val, curr.val - min_a)
          
      for child in [curr.left, curr.right]:
        if child:
          stack.append((child, max(max_a, curr.val), min(min_a, curr.val)))
    return max_v

Last Updated on 2024/04/20 by A1go