Leetcode 1026. Максимальная разница между узлом и предком

Классическая задача дерева с использованием рекурсии.

В чем проблема?

Нам дан корень бинарного дерева, и задача состоит в том, чтобы найти максимальное значение 'v' такое, что 'v' равно абсолютной разнице между двумя узлами 'a' и 'b', где 'a' является предком из «б».

Проще говоря, узел-предок «а» может быть родителем, прародителем, прапрадедушкой и т. д. узла «b» — предок — это любой узел, который находится между корнем и этим узлом, например:

                                   8
                                 /   \
                                3     10
                               / \      \
                              1   6      14
                                 /  \    /
                                4    7  13

В приведенном выше дереве предками узла 7 являются 6, 3 и 8, поскольку эти узлы находятся на пути от корня (8) к узлу 7.

Наша цель — найти пару узлов, где один является предком другого, а абсолютная разница их значений максимальна среди всех возможных пар предок-потомок в дереве.

Подход:

Поскольку мы работаем с древовидной структурой и учитываем родственные связи, отличным подходом является использование поиска в глубину (DFS). Для каждого узла мы хотим знать:

наименьшее значение, которое мы видели до сих пор
самое большое значение, которое мы видели до сих пор

Получив эту информацию для каждого узла, мы вычисляем абсолютную разницу между этими двумя значениями и обновляем наш ответ, если он больше, чем у нас есть до сих пор.

Вот пошаговая разбивка:

Начните с корневого узла. По мере того, как мы спускаемся по дереву, в каждом узле вычисляем абсолютную разницу между значением узла и минимальным и максимальным значениями, обнаруженными до сих пор. Это дает нам потенциальные ответы.
Обновите ответ с максимальным из этих различий.
Рекурсивно перемещайтесь по дереву, обновляя минимальное и максимальное значения, наблюдаемые до сих пор.

Код решения с построчным объяснением:

def dfs(node, min_val, max_val):
    # If the node is None (we've reached a leaf), we return the absolute difference between min_val and max_val.
    # This difference represents the maximum difference we've found in this particular path from root to leaf.
    if not node:
        return abs(max_val - min_val)
    
    # We update min_val and max_val with the current node's value.
    # This is because we're traversing down the tree, and we want to keep track of the smallest and largest values we've encountered so far.
    min_val = min(min_val, node.val)
    max_val = max(max_val, node.val)
    
    # We perform DFS for the left and right children of the current node.
    # For each child, we pass on the updated min_val and max_val. This lets each subtree know the smallest and largest values up to this point.
    # Each call to dfs will return the maximum absolute difference found in the corresponding subtree.
    left = dfs(node.left, min_val, max_val)
    right = dfs(node.right, min_val, max_val)
    
    # We want the single largest difference in the whole tree, so we return the maximum difference we found in either the left or the right subtree.
    return max(left, right)

# We start our DFS from the root node.
# Initially, we set our min_val to infinity and max_val to negative infinity since we haven't encountered any node yet.
return dfs(root, float('inf'), float('-inf'))

Только код решения:

def dfs(node, min_val, max_val):
    if not node:
        return abs(max_val - min_val)
    
    min_val = min(min_val, node.val)
    max_val = max(max_val, node.val)
    
    left = dfs(node.left, min_val, max_val)
    right = dfs(node.right, min_val, max_val)
    
    return max(left, right)

return dfs(root, float('inf'), float('-inf'))

Анализ сложности:

Временная сложность: O(n) — мы проходим каждый узел в дереве только один раз, поэтому временная сложность линейна по отношению к количеству узлов в дереве.

Пространственная сложность: O(h) — здесь мы используем рекурсивную поиск в глубину, и максимальная глубина рекурсии будет равна высоте дерева. Следовательно, сложность пространства будет пропорциональна высоте «h» дерева.

Если вам понравилась эта статья, рассмотрите возможность подписаться на меня, чтобы узнать больше. Ваши мысли и идеи важны для меня, и я приветствую любые предложения — чтобы сделать обмен вашими отзывами со мной еще проще, я создал быструю форму, доступ к которой вы можете получить здесь. Ваш вклад очень ценится! Не стесняйтесь обращаться к нам — ваше участие — это то, что делает это сообщество процветающим.

Спасибо за чтение и удачного кодирования! :)

Leetcode 1026. Максимальная разница между узлом и предком — Python.