Sprawdź, czy 2 węzły drzewa są powiązane (tj. Potomek-przodek)

rozwiąż go w czasie O (1), z przestrzenią O (N) (N = liczba węzłów)wstępne przetwarzanie jest dozwolone

to jest to! Pójdę do mojego rozwiązania (podejście) poniżej. Zatrzymaj się, jeśli chcesz się najpierw zastanowić.

W przypadku przetwarzania wstępnego postanowiłem wykonać zamówienie wstępne (najpierw rekurencyjnie przechodzić przez root, a następnie dzieci) i nadać etykietę każdemu węzłowi.

Pozwól mi wyjaśnić etykiety w szczegółach. Każda etykieta składa się z rozdzielonych przecinkami liczb naturalnych, takich jak „1,2,1,4,5” - długość tej sekwencji jest równa(głębokość węzła + 1). Na przykład. etykieta roota to „1”, dzieci roota będą miały etykiety „1,1”, „1,2”, „1,3” itd. Węzły następnego poziomu będą miały etykiety takie jak „1,1,1” , „1,1,2”, ..., „1,2,1”, „1,2,2”, ...

Zakładać, że "numer zamówienia„węzła to”1 indeks tego węzła„na liście dzieci swojego rodzica.

Wspólna reguła: etykieta węzła składa się z etykiety nadrzędnej, po której następuje przecinek i „numer zamówienia„węzła.

Tak więc, aby odpowiedzieć, czy dwa węzły są powiązane (tj. Potomek-potomek) w O (1), sprawdzę, czy etykieta jednego z nich jest „prefiks„etykiety drugiej. Chociaż nie jestem pewien, czy takie etykiety można uznać za zajmujące przestrzeń O (N).

Oczekuje się wszelkich krytyków z poprawkami lub alternatywnego podejścia.