Dado un entero N y un árbol N -ario de la siguiente forma:
- Cada Node se numera secuencialmente, desde el 1 hasta el último nivel, que contiene el Node N.
- Los Nodes en cada nivel impar contienen 2 hijos y los Nodes en cada nivel par contienen 4 hijos.
La tarea es imprimir la ruta desde el Node raíz hasta el Node N.
Ejemplos:
Entrada: N = 14
Salida: 1 2 5 14
Explicación: La ruta del Node 1 al Node 14 es 1 – > 2 – > 5 – > 14.Entrada: N = 11
Salida: 1 3 11
Explicación: La ruta del Node 1 al Node 11 es 1 – > 3 – > 11.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array para almacenar el número de Nodes presentes en cada nivel del Árbol , es decir, {1, 2, 8, 16, 64, 128…} y guárdelo.
- Calcule la suma del prefijo de la array, es decir, {1 3 11 27 91 219 …….}
- Encuentre el ind de índice en la array de suma de prefijos que excede o es igual a N usando lower_bound() . Por lo tanto, ind indica el número de niveles que deben atravesarse para llegar al Node N.
- Inicialice una variable, por ejemplo, temp = N y una ruta de array [] para almacenar los Nodes desde la raíz hasta N .
- Disminuya ind hasta que sea menor o igual a 1 y siga actualizando val = temp – prefix[ind – 1] .
- Actualizar temp = prefix[ind – 2] + (val + 1) / 2 si ind es impar.
- De lo contrario, actualice temp = prefix[ind – 2] + (val + 3) / 4 si ind es par.
- Agregue temp en la array path[] .
- Finalmente, imprima la array, ruta[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to find the path // from root to N void PrintPathNodes(ll N) { // Stores the number of // nodes at (i + 1)-th level vector<ll> arr; arr.push_back(1); // Stores the number of nodes ll k = 1; // Stores if the current // level is even or odd bool flag = true; while (k < N) { // If level is odd if (flag == true) { k *= 2; flag = false; } // If level is even else { k *= 4; flag = true; } // If level with // node N is reached if (k > N) { break; } // Push into vector arr.push_back(k); } ll len = arr.size(); vector<ll> prefix(len); prefix[0] = 1; // Compute prefix sums of count // of nodes in each level for (ll i = 1; i < len; ++i) { prefix[i] = arr[i] + prefix[i - 1]; } vector<ll>::iterator it = lower_bound(prefix.begin(), prefix.end(), N); // Stores the level in which // node N s present ll ind = it - prefix.begin(); ll temp = N; // Store path vector<int> path; path.push_back(N); while (ind > 1) { ll val = temp - prefix[ind - 1]; if (ind % 2 != 0) { temp = prefix[ind - 2] + (val + 1) / 2; } else { temp = prefix[ind - 2] + (val + 3) / 4; } --ind; // Insert temp into path path.push_back(temp); } if (N != 1) path.push_back(1); // Print path for (int i = path.size() - 1; i >= 0; i--) { cout << path[i] << " "; } } // Driver Code int main() { ll N = 14; // Function Call PrintPathNodes(N); return 0; }
Python3
# Python3 program for the above approach from bisect import bisect_left # Function to find the path # from root to N def PrintPathNodes(N): # Stores the number of # nodes at (i + 1)-th level arr = [] arr.append(1) # Stores the number of nodes k = 1 # Stores if the current # level is even or odd flag = True while (k < N): # If level is odd if (flag == True): k *= 2 flag = False # If level is even else: k *= 4 flag = True # If level with # node N is reached if (k > N): break # Push into vector arr.append(k) lenn = len(arr) prefix = [0]*(lenn) prefix[0] = 1 # Compute prefix sums of count # of nodes in each level for i in range(1,lenn): prefix[i] = arr[i] + prefix[i - 1] it = bisect_left(prefix, N) # Stores the level in which # node N s present ind = it temp = N # Store path path = [] path.append(N) while (ind > 1): val = temp - prefix[ind - 1] if (ind % 2 != 0): temp = prefix[ind - 2] + (val + 1) // 2 else: temp = prefix[ind - 2] + (val + 3) // 4 ind -= 1 # Insert temp into path path.append(temp) if (N != 1): path.append(1) # Print path for i in range(len(path)-1, -1, -1): print(path[i], end=" ") # Driver Code if __name__ == '__main__': N = 14 # Function Call PrintPathNodes(N) # This code is contributed by mohit kumar 29
Producción:
1 2 5 14
Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(log(N))
Publicación traducida automáticamente
Artículo escrito por pavang2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA