Пространственная сложность рекурсивного алгоритма обхода дерева

Question

Есть задача - проверить, что в бинарном дереве все узлы имеют одинаковое значение.

И есть эталонное решение при помощи рекурсии:

class Solution {
    public bool IsUnivalTree(TreeNode root) {
        bool left_correct = root.left == null ||
                (root.val == root.left.val && IsUnivalTree(root.left));
        bool right_correct = root.right == null ||
                (root.val == root.right.val && IsUnivalTree(root.right));
        return left_correct && right_correct;
    }
}

Работает... Но есть у меня сомнения, что в статье правильно указана сложность:

Time Complexity: O(N), where N is the number of nodes in the given tree.

Space Complexity: O(H), where H is the height of the given tree.

Моё видение такое: пространственная сложность должна быть тоже O(N), так как в худшем случае все элементы могут быть выстроены друг под другом и нужно учитывать и такой случай.

Но я что-то сомневаюсь... Расчёт худшего кейса это уже не нотация О-большое?

Это правильная логика, если нет, то почему?

Answer 1

Пусть H(root) высота дерева. Сколько места требуется для вычисления IsUnivalTree? Потребное место обозначим как S(root). S(null) примем за ноль. Сам вызов IsUnivalTree требует единицу - данные одного вызова занимают константную память. Память для выполнения первого оператора есть 1 + S(root.left). Память для второго оператора 1 + S(root.right). Операторы выполняются последовательно, общая память есть max(1 + S(root.left), 1 + S(root.right)). Упрощаем 1 + max(S(root.left), S(root.right)).

Индукция: база очевидна. Переход: если S(root.left) <= H(root.left) и S(root.right) <= H(root.right), то S(root) <= H(root). Это следует из H(root) = 1 + max(H(root.left), H(root.right)).

Что и требовалось доказать. Заметим что в доказательстве не используется N - размер дерева, только его высота H. То что между N и H тоже есть соотношение - дело второе.

БЛОГ НА HUSL

Пространственная сложность рекурсивного алгоритма обхода дерева

Ответы (1 шт):