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>
Producción:
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