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:
- 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.
- 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.
- 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.
- 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
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)