maximum difference between node and ancestor
1 class Solution: 2 def maxAncestorDiff(self, root): 3 def dfs(self, n, mn, mx): 4 if not n: 5 return 0 6 new_mn = min(n.val, mn) 7 new_mx = max(n.val, mx) 8 return max( 9 max(abs(n.val - mn), abs(n.val - mx)), 10 dfs(n.left, new_mn, new_mx), 11 dfs(n.right, new_mn, new_mx), 12 ) 13 14 return dfs(root, root.val, root.val)
The mistake i made on this problem was to take a bottom up approach rather than a top down approach.
The bottom up approach was too complex, as you're basically uncertain whether you have a left child, a right child, both, or neither.
Making queries like
node.left.val is totally impossible and it was a huge mistake even trying to do such a thing.
In this implementation (above) the base case gracefully handles children not existing, and the top down approach leads to very clean code.