Longitud del camino recto más largo desde un árbol binario dado

Dado un árbol binario , la tarea es encontrar la longitud del camino recto más largo del árbol binario dado.

El camino recto se define como el camino que comienza desde cualquier Node y termina en otro Node en el árbol, de modo que la dirección de recorrido desde el Node de origen hasta el Node de destino siempre permanece igual, es decir, a la izquierda o a la derecha, sin ningún cambio en la dirección. es decir izquierda->izquierda ->izquierda o derecha->derecha->dirección derecha. 

Ejemplos:

Aporte:

Salida: 2
Explicación:
El camino que se muestra en verde es el camino recto más largo de 4 a 6 que tiene una longitud de 2. 
 

Aporte:

Salida: 3
Explicación:
El camino que se muestra en verde es el camino recto más largo de 5 a 0 que tiene una longitud de 3. 
 

Enfoque: La idea es utilizar el recorrido Postorder . Siga los pasos a continuación para resolver el problema:

  1. Para cada Node, verifique la dirección del Node actual (ya sea hacia la izquierda o hacia la derecha) y verifique qué dirección de su hijo proporciona la longitud más larga debajo de ese Node.
  2. Si la dirección del Node actual y el hijo que da la longitud más larga no es la misma, guarde el resultado de ese hijo y pase la longitud del otro hijo a su padre.
  3. Usando los pasos anteriores, encuentre el camino recto más largo en cada Node y guarde el resultado para imprimir el valor máximo entre todos los caminos rectos.
  4. Imprima la ruta máxima después de los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

Bloque de código

Producción: 

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por arpit7714 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *