Maximum Difference Between Node and Ancestor

Intuition

For each node, to get the maximum difference whose ancestor is the current node, we need to know the maximum value and minimum value in its sub-tree.

So we could solve this problem by using DFS with 3 additional return values.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        return self._helper(root)[-1]

    def _helper(self, node):
        if node.right is None and node.left is None:
            return node.val, node.val, 0
        maximum = minimum = node.val
        max_diff = 0
        if node.left:
            tmp = self._helper(node.left)
            max_diff = max(abs(tmp[0] - node.val),
                    abs(tmp[1] - node.val),
                    tmp[2],
                    max_diff)
            maximum = max(tmp[0], maximum)
            minimum = min(tmp[1], minimum)
        if node.right:
            tmp = self._helper(node.right)
            max_diff = max(abs(tmp[0] - node.val),
                    abs(tmp[1] - node.val),
                    tmp[2],
                    max_diff)
            maximum = max(tmp[0], maximum)
            minimum = min(tmp[1], minimum)
        return maximum, minimum, max_diff