Dado un árbol binario que consta de N Nodes, la tarea es imprimir el recorrido de orden de nivel después de reemplazar el valor de cada Node con su potencia más cercana al valor mínimo del nivel anterior en el árbol original.
Nota: Para cualquier caso de dos potencias más próximas, seleccione la máxima entre ellas.
Ejemplos:
Entrada: 7
/ \
4 11
/
23
Salida: 7 4 11 23 N
Explicación:
- El valor del Node en el nivel 0 permanece sin cambios, es decir, 7.
- La potencia de 7 más cercana a 4 es 7 1 = 7.
La potencia de 7 más cercana a 11 es 7 1 = 7.
Por lo tanto, los Nodes en el nivel 1 se convierten en {7, 7}.- El valor mínimo del Node en el nivel 1 es 4.
La potencia de 4 más cercana a 23 es 4 4 = 16.
Por lo tanto, el Node en el nivel 2 se convierte en {16}.El árbol resultante después de completar las operaciones anteriores es el siguiente:
7
/ \
4 11
/
23Entrada: 3
/ \
2 6
/ \ \
45 71 25
Salida: 3 3 9 32 64 N 32
Enfoque: La idea es realizar el Traversal de Orden de Nivel usando una Cola para resolver el problema.
Siga los pasos a continuación para resolver el problema:
- Defina una función, digamos nativePow(X, Y), para encontrar la potencia más cercana de un entero Y :
- Encuentre log(X) base Y y guárdelo en una variable, digamos K .
- Devuelve Y K si abs(X – Y K ) es menor que abs(Y (K + 1) – X) . De lo contrario, devuelva Y (K + 1) .
- Inicialice dos variables, digamos minCurr y minPrev, para almacenar el valor mínimo del nivel actual y el valor mínimo del nivel anterior respectivamente.
- Inicialmente, asigne minPrev = root.val e inicialice una cola, diga Q para almacenar los Nodes para el cruce de orden de nivel.
- Iterar mientras Q no está vacío() :
- Almacene el primer Node de la cola en una variable, digamos temp , y elimine el primer Node de la cola Q .
- Asigne el valor de minCurr a minPrev y actualice minCurr = 10 18 .
- Itere sobre el rango [0, length(Q) – 1] y actualice minCurr como minCurr = min(minCurr, temp.val) y asigne la potencia más cercana del entero minPrev a temp.val .
- En cada iteración del paso anterior, presione temp.left y temp.right si los Nodes respectivos no son NULL .
- Después de completar los pasos anteriores, imprima el recorrido de orden de niveles del árbol actualizado.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program for the above approach import math # Structure of a Node of a Tree class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # Function to calculate the # nearest power of an integer def nearestPow(x, base): k = int(math.log(x, base)) if abs(base**k - x) < abs(base**(k+1) - x): return base**k else: return base**(k+1) # Iterative method to perform # Level Order Traversal def printLevelOrder(root): # Base Case if root is None: return # Queue for Level # Order Traversal q = [] # Enqueue root q.append(root) while q: # Stores number of # nodes at current level count = len(q) # Dequeue all nodes of the current # level and Enqueue all nodes of # the next level while count > 0: temp = q.pop(0) print(temp.val, end=' ') # Push the left subtree # if not empty if temp.left: q.append(temp.left) # Push the right subtree # if not empty if temp.right: q.append(temp.right) # Decrement count by 1 count -= 1 # Function to replace each node # with nearest power of minimum # value of previous level def replaceNodes(root): # Stores the nodes of tree to # traverse in level order que = [root] # Stores current level lvl = 1 # Stores the minimum # value of previous level minPrev = root.val # Stores the minimum # value of current level minCurr = root.val # Iterate while True while True: # Stores length of queue length = len(que) # If length is zero if not length: break # Assign minPrev = minCurr minPrev = minCurr minCurr = 1000000000000000000 # Iterate over range [0, length - 1] while length: # Stores current node of tree temp = que.pop(0) # Update minCurr minCurr = min(temp.val, minCurr) # Replace current node with # nearest power of minPrev temp.val = nearestPow(temp.val, minPrev) # Left child is not Null if temp.left: # Append temp.left node # in the queue que.append(temp.left) # If right child is not Null if temp.right: # Append temp.right node # in the queue que.append(temp.right) # Decrement length by one length -= 1 # Increment level by one lvl += 1 # Function Call to perform the # Level Order Traversal printLevelOrder(root) # Driver Code # Given Tree root = TreeNode(7) root.left = TreeNode(4) root.right = TreeNode(11) root.left.right = TreeNode(23) replaceNodes(root)
Javascript
<script> // JavaScript program for the above approach // Structure of a Node of a Tree class TreeNode{ constructor(val = 0, left = null, right = null){ this.val = val this.left = left this.right = right } } // Function to calculate the // nearest power of an integer function nearestPow(x, base){ let k = Math.floor(Math.log(x)/ Math.log(base)) if(Math.abs(Math.pow(base,k) - x) < Math.abs(Math.pow(base,k+1) - x)) return Math.pow(base,k) else return Math.pow(base,k+1) } // Iterative method to perform // Level Order Traversal function printLevelOrder(root){ // Base Case if(root == null) return // Queue for Level // Order Traversal let q = [] // Enqueue root q.push(root) while(q){ // Stores number of // nodes at current level let count = q.length // Dequeue all nodes of the current // level and Enqueue all nodes of // the next level while(count > 0){ let temp = q.shift() document.write(temp.val,' ') // Push the left subtree // if not empty if(temp.left) q.push(temp.left) // Push the right subtree // if not empty if(temp.right) q.push(temp.right) // Decrement count by 1 count -= 1 } } } // Function to replace each node // with nearest power of minimum // value of previous level function replaceNodes(root){ // Stores the nodes of tree to // traverse in level order let que = [root] // Stores current level let lvl = 1 // Stores the minimum // value of previous level let minPrev = root.val // Stores the minimum // value of current level let minCurr = root.val // Iterate while True while(true){ // Stores length of queue let Length = que.length // If length is zero if(!Length) break // Assign minPrev = minCurr minPrev = minCurr minCurr = 1000000000000000000 // Iterate over range [0, length - 1] while(Length){ // Stores current node of tree let temp = que.shift() // Update minCurr minCurr = Math.min(temp.val, minCurr) // Replace current node with // nearest power of minPrev temp.val = nearestPow(temp.val, minPrev) // Left child is not Null if(temp.left) // Append temp.left node // in the queue que.push(temp.left) // If right child is not Null if(temp.right) // Append temp.right node // in the queue que.push(temp.right) // Decrement length by one Length-- } // Increment level by one lvl++ } // Function Call to perform the // Level Order Traversal printLevelOrder(root) } // Driver Code // Given Tree let root = new TreeNode(7) root.left = new TreeNode(4) root.right = new TreeNode(11) root.left.right = new TreeNode(23) replaceNodes(root) // This code is contributed by shinjanpatra </script>
7 7 7 16
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA