Решение LCA методами из книги Cracking The Coding Interview
Возвращаясь к способам решения проблемы наименьшего общего предка в бинарном дереве (lowest common ancestor), затронутым в Телефонное интервью с Facebook 2014.07.21, 2-й вопрос, хотелось бы прокомментировать освещение данного вопроса в книге Cracking The Coding Interview.
У меня есть два издания данной книги, v4 и v5. В обоих, как один из вариантов, предлагается решение следующим путем: начиная с корня дерева, выяснить, находятся ли обе ноды в одном и том же поддереве (слева или справа). В случае, если ноды в разных поддеревьях, проверяемая нода является их наименьшим общим предком. В противном случае, проверить таким же образом корень поддерева, в котором находятся обе искомые ноды.
Проблема этого решения в том, что для каждой такой проверки требуется проход по всему дереву, корень которого проверяется на предмет того, является ли он LCA. При каждой неудачной попытке (когда обе ноды в одном и том же поддереве), мы спускаемся на один уровень в дереве и проверяем меньшее поддерево. Time complexity данной процедуры будет составлять O(N log N), где N - количество нод в дереве.
4-е издание не дает никаких комментариев по поводу time complexity, а вот в 5-м я обнаружил следующее:
This algorithm runs in O(n) time on a balanced tree. This is because covers is called on 2n nodes in the first call (n nodes for the left side, and n nodes for the right side). After that, the algorithm branches left or right, at which point covers will be called on 2n/2 nodes, then 2n/4, and so on. This results in a runtime of O(n).
Довольно странно, когда вначале дается, можно сказать, словарное определение time complexity O(N log N), и затем неожиданно делается вывод о том, что time complexity O(N). С моей точки зрения, это ошибка в книге.
Издание 5 также дает оптимизированный алгоритм, время выполнения которого на самом деле O(N), и при этом он делает всего один проход по дереву. Суть его в специальной процедуре прохода по дереву, которая ищет сразу обе ноды и возвращает результат в зависимости от того, найдена ли лишь одна из них, и если найдены обе, то возвращаемый результат является наименьшим общим предком. Таким способом это решается за один проход.
Моя имплементация изложенных в книге алгоритмов:
1) С помощью covers (я все-таки настаиваю, что время для этого решения будет O(N log N))
https://gist.github.com/codekrolik/ae4f59d472c2a46d5907
2) Оптимизированный алгоритм, O(N) в один проход по дереву.
https://gist.github.com/codekrolik/3427aa68eb2ac4d82bc6
3) Тесты для всех решений (включая мое оригинальное)