Maximum Difference Between Node and Ancestor

Problem Id: 1026 Difficulty: Medium Tag: Tree Tag: Depth-first Search


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