LC 1026 [M] Maximum Difference Between Node and Ancestor - ALawliet/algorithms GitHub Wiki
DFS top-down, preorder
here we just need the ancestor NOT the lowest common ancestor, so we don't have to go down then up (bottom-up, post-order) we just have to go down (top-down, pre-order)
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
def preorder(node, hi, lo):
if not node: return hi - lo
hi, lo = max(hi, node.val), min(lo, node.val)
L = preorder(node.left, hi, lo)
R = preorder(node.right, hi, lo)
return max(L, R)
return preorder(root, root.val, root.val)