Verificar se dois nós da árvore estão relacionados (isto é, descendentes dos ancestrais)

resolva-o em O (1) tempo, com O (N) espaço (N = # de nós)o pré-processamento é permitido

É isso aí. Eu vou para a minha solução (abordagem) abaixo. Por favor, pare se você quiser se pensar primeiro.

Para um pré-processamento, decidi fazer uma pré-ordem (percorrer a raiz primeiro, depois os filhos) e dar um rótulo para cada nó.

Deixe-me explicar os rótulos em detalhes. Cada rótulo consistirá de números naturais separados por vírgula, como "1,2,1,4,5" - o comprimento dessa seqüência é igual a(a profundidade do nó + 1). Por exemplo. o rótulo da raiz é "1", os filhos do root terão rótulos "1,1", "1,2", "1,3" etc. Os nós do próximo nível terão rótulos como "1,1,1" , "1,1,2", ..., "1,2,1", "1,2,2", ...

Assuma isso "o número do pedido"de um nó é o"Índice baseado em 1 deste nó"na lista de filhos de seus pais.

Regra comum: o rótulo do nó consiste em seu rótulo pai seguido por vírgula e "o número do pedido"do nó.

Assim, para responder se dois nós estão relacionados (ou seja, ancestral descendente) em O (1), eu vou verificar se o rótulo de um deles é "um prefixo"do rótulo do outro. Embora eu não tenha certeza se esses rótulos podem ser considerados para ocupar o espaço O (N).

Quaisquer críticos com correções ou uma abordagem alternativa são esperados.