Проверить, связаны ли 2 узла дерева (предок/потомок )в O (1 )с предварительной обработкой -

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

• решить его за O (1 )раз, с O (N )пространством (N = #узлов)
• разрешена предварительная -обработка

Вот и все. Я перейду к моему решению (подходу )ниже. Пожалуйста, остановитесь, если хотите сначала подумать о себе.

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

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

Предположим, что "номер заказа " узла является " 1 -индекс этого узла " в дочернем списке его родителя.

Общее правило :Метка узла состоит из его родительской метки, за которой следует запятая и " порядковый номер " узла.

Таким образом, чтобы ответить, связаны ли два узла (, то есть предок -потомок )в O (1 ), я буду проверять, является ли метка одного из них " префикс "другой метки. Хотя я не уверен, можно ли считать, что такие метки занимают O (N )места.

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