Dado un árbol binario enraizado en el Node 1, la tarea es imprimir los elementos en el siguiente orden definido. Primero, imprima todos los elementos del último nivel de una manera alternativa, por ejemplo, primero imprime el elemento más a la izquierda y luego el elemento más a la derecha y continúa así hasta que … Continue reading «Recorrido de izquierda a derecha de todos los niveles del árbol binario»
Dado un árbol n-ario, cuente el número de formas de atravesar un árbol n-ario (o un gráfico acíclico dirigido) comenzando desde el vértice de la raíz. Supongamos que tenemos un árbol N-ario dado como se muestra a continuación. C++ // C++ program to find the number of ways to traverse a // n-ary tree starting … Continue reading «Número de formas de atravesar un árbol N-ario»
Dados dos árboles N-arios que tienen M Nodes cada uno. También, dadas sus aristas y sus raíces respectivamente. La tarea es comprobar si son árboles isomorfos o no. Si ambos árboles son isomorfos, imprima «Sí» , de lo contrario, imprima «No» . Ejemplos: Entrada: M = 9, Node raíz del árbol-1: 1, Node raíz del … Continue reading «Isomorfismo en árboles N-arios»
Dado un árbol de N-arrays de N Nodes, con raíz en 1 , con bordes en la forma {u, v} , y una array de valores[] que consta de N enteros. Cada vértice i tiene un valor entero indicado por valores[i] . La tarea es encontrar la suma de subárbol más grande posible para cada … Continue reading «Mayor suma de subárboles para cada vértice del árbol N-ario dado»
Dado un árbol, y los pesos de todos los Nodes y un número entero x , la tarea es encontrar un Node i tal que |weight[i] – x| es máximo. Ejemplos: Aporte: x = 15 Salida: 1 Node 1: |5 – 15| = 10 Node 2: |10 – 15| = 5 Node 3: |11 -15| … Continue reading «Encuentra el Node cuya diferencia absoluta con X da el valor máximo»
Dado un árbol N-ario que consta de N Nodes con valores de 1 a N enraizados en 1, para todos los Nodes, imprima el número de ancestros que tienen un valor menor que el Node actual. Ejemplo: Entrada: A continuación se muestra el árbol dado: … Continue reading «Recuento de ancestros con menor valor para cada Node de un árbol N-ario»
Dado un árbol N-ario que contiene, la tarea es imprimir el recorrido en orden del árbol. Ejemplos: Entrada: N = 3 Salida: 5 6 2 7 3 1 4 Entrada: N = 3 Salida: 2 5 3 1 4 6 Enfoque: El recorrido en orden de un árbol N-ario se define como visitar todos los … Continue reading «Recorrido en orden de un árbol N-ario»
Hemos visto varios métodos con diferentes complejidades de tiempo para calcular LCA en un árbol n-ario: Método 1: método ingenuo (mediante el cálculo de la ruta de la raíz al Node) | O(n) por consulta Método 2: uso de la descomposición Sqrt | O(sqrt H) Método 3: Uso del enfoque de DP de array dispersa … Continue reading «ACV para árbol n-ario | Consulta constante O(1)»
Dado un árbol genérico que consiste en N Nodes valorados de 0 a (N – 1) donde P[i] th en la array P[] denota i th Nodes padre (indexación basada en 1) . Cada i -ésimo Node tiene un peso adjunto, dado en la array W[] . La tarea es encontrar un par de Nodes … Continue reading «Maximizar la diferencia entre un par de Nodes en un árbol enraizado dado, de modo que un Node sea el ancestro de otro»
Dada una array de pesos[] que consta de N enteros positivos, donde pesos[i] denota el peso del i -ésimo Node, la tarea es construir un árbol N-ario tal que no haya dos Nodes conectados directamente que tengan el mismo peso. Si es posible hacer un árbol de este tipo, imprima «Sí» junto con sus bordes. … Continue reading «Construya un árbol N-ario que no tenga un par de Nodes adyacentes con el mismo peso a partir de pesos dados»