---
title: "Решение LCA методами из книги Cracking The Coding Interview"
description: "Возвращаясь к способам решения проблемы наименьшего общего предка в бинарном дереве (lowest common a..."
author: "codekrolik"
published: "2014-07-23T23:30:33+00:00"
modified: "2014-07-24T00:00:35+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/reshenie-lca-metodami-iz-knigi-cracking-the-coding-interview-422534"
markdown_url: "https://yvision.kz/post/reshenie-lca-metodami-iz-knigi-cracking-the-coding-interview-422534/markdown"
site_name: "Yvision.kz"
---

# Решение LCA методами из книги Cracking The Coding Interview

> Возвращаясь к способам решения проблемы наименьшего общего предка в бинарном дереве (lowest common a...

Возвращаясь к способам решения проблемы наименьшего общего предка в бинарном дереве (lowest common ancestor), затронутым в [Телефонное интервью с Facebook 2014.07.21, 2-й вопрос](http://codekrolik.yvision.kz/post/422422), хотелось бы прокомментировать освещение данного вопроса в книге 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](https://gist.github.com/codekrolik/ae4f59d472c2a46d5907)

 

2) Оптимизированный алгоритм, O(N) в один проход по дереву.

[https://gist.github.com/codekrolik/3427aa68eb2ac4d82bc6](https://gist.github.com/codekrolik/3427aa68eb2ac4d82bc6)

 

3) Тесты для всех решений (включая мое оригинальное)

[https://gist.github.com/codekrolik/2c2b9badeb45bb72fc3f](https://gist.github.com/codekrolik/2c2b9badeb45bb72fc3f)

---

Source: [https://yvision.kz/post/reshenie-lca-metodami-iz-knigi-cracking-the-coding-interview-422534](https://yvision.kz/post/reshenie-lca-metodami-iz-knigi-cracking-the-coding-interview-422534)