Проверьте, связаны ли 2 узла дерева (т. Е. Потомок-предок)

solve it in O(1) time, with O(N) space (N = # of nodes) pre-processing is allowed

That's it. I'll be going to my solution (approach) below. Please stop if you want to think yourself first.

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

Позвольте мне объяснить метки в деталях. Каждая метка будет состоять из разделенных запятыми натуральных чисел, таких как «1,2,1,4,5» - длина этой последовательности равна(the depth of the node + 1), Например. метка корня является «1», дочерние элементы корня будут иметь метки «1,1», «1,2», «1,3»; и т. д. Узлы следующего уровня будут иметь метки, подобные «1,1,1», «1,1,2», ..., «1,2,1», «1,2,2»; ...

Предположим, что & quot;the order number& Quot; узла является & quot;1-based index of this node& Quot; в списке детей его родителя.

Общее правило: метка узла состоит из его родительской метки, за которой следуют запятая и & quot;the order number& Quot; узла.

Таким образом, чтобы ответить, связаны ли два узла (т. Е. Предка-потомка) в O (1), я 'проверю, является ли метка одного из них & quot;a prefix& Quot; другой метки. Хотя я не уверен, можно ли считать, что такие метки занимают O (N) место.

Ожидается любая критика с исправлениями или альтернативный подход.