Compruebe si 2 nodos de árbol están relacionados (es decir, descendiente de ancestro)

resuélvalo en tiempo O (1), con espacio O (N) (N = número de nodos)se permite el preprocesamiento

Eso es. Voy a ir a mi solución (enfoque) a continuación. Por favor, detente si quieres pensar primero en ti mismo.

Para un preprocesamiento, decidí hacer un pedido anticipado (recursivamente ir primero a través de la raíz, luego a los hijos) y asignar una etiqueta a cada nodo.

Déjame explicarte las etiquetas en detalle. Cada etiqueta constará de números naturales separados por comas como "1,2,1,4,5" - la longitud de esta secuencia es igual a(La profundidad del nodo + 1). P.ej. la etiqueta de la raíz es "1", los hijos de la raíz tendrán etiquetas "1,1", "1,2", "1,3", etc. Los nodos del siguiente nivel tendrán etiquetas como "1,1,1" , "1,1,2", ..., "1,2,1", "1,2,2", ...

Asumir que "el numero de orden"de un nodo es el"Índice basado en 1 de este nodo"en la lista de hijos de su padre.

Regla común: la etiqueta del nodo consiste en su etiqueta principal seguida de una coma y "el numero de orden"del nodo.

Por lo tanto, para responder si dos nodos están relacionados (es decir, antepasado-descendiente) en O (1), verificaré si la etiqueta de uno de ellos es "un prefijo"de la etiqueta del otro. Aunque no estoy seguro de si se puede considerar que dichas etiquetas ocupan un espacio O (N).

Se espera cualquier crítica con arreglos o un enfoque alternativo.