Problem Statement
leetcode problem link
Brute Force [Accepted]
# 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
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
res = [0]
def dfs(node, res):
if not node:
return
helper(node.left, node.val, res)
helper(node.right, node.val, res)
dfs(node.left, res)
dfs(node.right, res)
def helper(node, val, curr):
if not node:
return float('inf')
curr[0] = max(curr[0], abs(val - node.val))
helper(node.left, val, curr)
helper(node.right, val, curr)
dfs(root, res)
return res[0]
Editorial
Approach #1: Recursion
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
if not root:
return 0
# record the required maximum difference
self.result = 0
def helper(node, cur_max, cur_min):
if not node:
return
# update `result`
self.result = max(self.result, abs(cur_max-node.val),
abs(cur_min-node.val))
# update the max and min
cur_max = max(cur_max, node.val)
cur_min = min(cur_min, node.val)
helper(node.left, cur_max, cur_min)
helper(node.right, cur_max, cur_min)
helper(root, root.val, root.val)
return self.result
Approach #2: Maximum Minus Minimum
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
if not root:
return 0
def helper(node, cur_max, cur_min):
# if encounter leaves, return the max-min along the path
if not node:
return cur_max - cur_min
# else, update max and min
# and return the max of left and right subtrees
cur_max = max(cur_max, node.val)
cur_min = min(cur_min, node.val)
left = helper(node.left, cur_max, cur_min)
right = helper(node.right, cur_max, cur_min)
return max(left, right)
return helper(root, root.val, root.val)
