Dado un árbol binario que consiste en N Nodes, la tarea es reemplazar todos los Nodes que están presentes en los niveles pares en un árbol binario con su cuadrado perfecto par más cercano y reemplazar los Nodes en los niveles impares con su cuadrado perfecto impar más cercano .
Ejemplos:
Entrada: 5
/ \
3 2
/ \
16 19Salida: 9
/ \
4 4
/ \
9 25Explicación:
Nivel 1: El cuadrado perfecto impar más cercano a 5 es 9.
Nivel 2: El cuadrado perfecto par más cercano a 3 y 2 son 4.
Nivel 3: El cuadrado perfecto impar más cercano a 16 es 9 y a 19 es 25.Entrada: 45
/ \
65 32
/
89Salida: 49
/ \
64 36
/
81Explicación:
Nivel 1: El cuadrado perfecto impar más cercano a 45 es 49.
Nivel 2: El cuadrado perfecto par más cercano a 65 y 32 son 64 y 36 respectivamente.
Nivel 3: El cuadrado perfecto impar más cercano a 89 es 81.
Enfoque: El problema dado se puede resolver usando Level Order Traversal . Siga los pasos a continuación para resolver el problema:
- Inicialice una cola , diga q.
- Empuje la raíz en la cola.
- Bucle mientras la cola no está vacía
- Almacene el Node actual en una variable, digamos temp_node .
- Si el valor del Node actual es un cuadrado perfecto , verifique lo siguiente:
- Si el valor del nivel es impar y el valor del Node actual es par, encuentre el cuadrado perfecto impar más cercano y actualice temp_node→data .
- Si el valor del nivel es par y el valor del Node actual es impar, encuentre el cuadrado perfecto par más cercano y actualice temp_node→data .
- De lo contrario, encuentre el cuadrado perfecto impar más cercano si el valor del nivel es impar o el cuadrado perfecto par más cercano si el valor del nivel es par. Actualice temp_node→data .
- Imprimir temp_node→datos .
- Encola los hijos de temp_node (primero el hijo izquierdo , luego el hijo derecho ) a q , si existe.
- Retire el Node actual de q .
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; // Structure of a // Binary Tree Node struct Node { int data; struct Node *left, *right; }; // Function to replace all nodes // at even and odd levels with their // nearest even or odd perfect squares void LevelOrderTraversal(Node* root) { // Base Case if (root == NULL) return; // Create an empty queue // for level order traversal queue<Node*> q; // Enqueue root q.push(root); // Initialize height int lvl = 1; // Iterate until queue is not empty while (q.empty() == false) { // Store the size // of the queue int n = q.size(); // Traverse in range [1, n] for (int i = 0; i < n; i++) { // Store the current node Node* node = q.front(); // Store its square root double num = sqrt(node->data); int x1 = floor(num); int x2 = ceil(num); // Check if it is a perfect square if (x1 == x2) { // If level is odd and value is even, // find the closest odd perfect square if ((lvl & 1) && !(x1 & 1)) { int num1 = x1 - 1, num2 = x1 + 1; node->data = (abs(node->data - num1 * num1) < abs(node->data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } // If level is even and value is odd, // find the closest even perfect square if (!(lvl & 1) && (x1 & 1)) { int num1 = x1 - 1, num2 = x1 + 1; node->data = (abs(node->data - num1 * num1) < abs(node->data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } } // Otherwise, find the find // the nearest perfect square else { if (lvl & 1) node->data = (x1 & 1) ? (x1 * x1) : (x2 * x2); else node->data = (x1 & 1) ? (x2 * x2) : (x1 * x1); } // Print front of queue // and remove it from queue cout << node->data << " "; q.pop(); // Enqueue left child if (node->left != NULL) q.push(node->left); // Enqueue right child if (node->right != NULL) q.push(node->right); } // Increment the level by 1 lvl++; cout << endl; } } // Utility function to // create a new tree node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Driver Code int main() { // Binary Tree Node* root = newNode(5); root->left = newNode(3); root->right = newNode(2); root->right->left = newNode(16); root->right->right = newNode(19); LevelOrderTraversal(root); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; // Structure of a // Binary Tree Node class Node { int data; Node left, right; Node(int data) { this.data = data; left = right = null; } } class GFG{ // Function to replace all nodes // at even and odd levels with their // nearest even or odd perfect squares static void LevelOrderTraversal(Node root) { // Base Case if (root == null) return; // Create an empty queue // for level order traversal Queue<Node> q = new LinkedList<>(); // Enqueue root q.add(root); // Initialize height int lvl = 1; // Iterate until queue is not empty while (q.size() != 0) { // Store the size // of the queue int n = q.size(); // Traverse in range [1, n] for(int i = 0; i < n; i++) { // Store the current node Node node = q.peek(); // Store its square root double num = Math.sqrt(node.data); int x1 = (int)Math.floor(num); int x2 = (int)Math.ceil(num); // Check if it is a perfect square if (x1 == x2) { // If level is odd and value is even, // find the closest odd perfect square if (((lvl & 1) != 0) && !((x1 & 1) != 0)) { int num1 = x1 - 1, num2 = x1 + 1; node.data = (Math.abs(node.data - num1 * num1) < Math.abs(node.data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } // If level is even and value is odd, // find the closest even perfect square if (!((lvl & 1) != 0) && ((x1 & 1) != 0)) { int num1 = x1 - 1, num2 = x1 + 1; node.data = (Math.abs(node.data - num1 * num1) < Math.abs(node.data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } } // Otherwise, find the find // the nearest perfect square else { if ((lvl & 1) != 0) node.data = (x1 & 1) != 0 ? (x1 * x1) : (x2 * x2); else node.data = (x1 & 1) != 0 ? (x2 * x2) : (x1 * x1); } // Print front of queue // and remove it from queue System.out.print(node.data + " "); q.poll(); // Enqueue left child if (node.left != null) q.add(node.left); // Enqueue right child if (node.right != null) q.add(node.right); } // Increment the level by 1 lvl++; System.out.println(); } } // Driver Code public static void main (String[] args) { // Binary Tree Node root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.right.left = new Node(16); root.right.right = new Node(19); LevelOrderTraversal(root); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach from collections import deque from math import sqrt, ceil, floor # Structure of a # Binary Tree Node class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Function to replace all nodes # at even and odd levels with their # nearest even or odd perfect squares def LevelOrderTraversal(root): # Base Case if (root == None): return # Create an empty queue # for level order traversal q = deque() # Enqueue root q.append(root) # Initialize height lvl = 1 # Iterate until queue is not empty while (len(q) > 0): # Store the size # of the queue n = len(q) # Traverse in range [1, n] for i in range(n): # Store the current node node = q.popleft() # Store its square root num = sqrt(node.data) x1 = floor(num) x2 = ceil(num) # Check if it is a perfect square if (x1 == x2): # If level is odd and value is even, # find the closest odd perfect square if ((lvl & 1) and not (x1 & 1)): num1, num2 = x1 - 1, x1 + 1 node.data = (num1 * num1) if (abs(node.data - num1 * num1) < abs(node.data - num2 * num2)) else (num2 * num2) # If level is even and value is odd, # find the closest even perfect square if (not (lvl & 1) and (x1 & 1)): num1,num2 = x1 - 1, x1 + 1 node.data = (num1 * num1) if (abs(node.data - num1 * num1) < abs(node.data - num2 * num2)) else (num2 * num2) # Otherwise, find the find # the nearest perfect square else: if (lvl & 1): node.data = (x1 * x1) if (x1 & 1) else (x2 * x2) else: node.data = (x2 * x2) if (x1 & 1) else (x1 * x1) # Prfront of queue # and remove it from queue print(node.data, end = " ") # Enqueue left child if (node.left != None): q.append(node.left) # Enqueue right child if (node.right != None): q.append(node.right) # Increment the level by 1 lvl += 1 print() # Driver Code if __name__ == '__main__': # Binary Tree root = Node(5) root.left = Node(3) root.right = Node(2) root.right.left = Node(16) root.right.right = Node(19) LevelOrderTraversal(root) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Collections.Generic; // Structure of a // Binary Tree Node public class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } public class GFG { // Function to replace all nodes // at even and odd levels with their // nearest even or odd perfect squares static void LevelOrderTraversal(Node root) { // Base Case if (root == null) return; // Create an empty queue // for level order traversal Queue<Node> q = new Queue<Node>(); // Enqueue root q.Enqueue(root); // Initialize height int lvl = 1; // Iterate until queue is not empty while (q.Count != 0) { // Store the size // of the queue int n = q.Count; // Traverse in range [1, n] for(int i = 0; i < n; i++) { // Store the current node Node node = q.Peek(); // Store its square root double num = Math.Sqrt(node.data); int x1 = (int)Math.Floor(num); int x2 = (int)Math.Ceiling(num); // Check if it is a perfect square if (x1 == x2) { // If level is odd and value is even, // find the closest odd perfect square if (((lvl & 1) != 0) && !((x1 & 1) != 0)) { int num1 = x1 - 1, num2 = x1 + 1; node.data = (Math.Abs(node.data - num1 * num1) < Math.Abs(node.data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } // If level is even and value is odd, // find the closest even perfect square if (!((lvl & 1) != 0) && ((x1 & 1) != 0)) { int num1 = x1 - 1, num2 = x1 + 1; node.data = (Math.Abs(node.data - num1 * num1) < Math.Abs(node.data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } } // Otherwise, find the find // the nearest perfect square else { if ((lvl & 1) != 0) node.data = (x1 & 1) != 0 ? (x1 * x1) : (x2 * x2); else node.data = (x1 & 1) != 0 ? (x2 * x2) : (x1 * x1); } // Print front of queue // and remove it from queue Console.Write(node.data + " "); q.Dequeue(); // Enqueue left child if (node.left != null) q.Enqueue(node.left); // Enqueue right child if (node.right != null) q.Enqueue(node.right); } // Increment the level by 1 lvl++; Console.WriteLine(); } } // Driver Code static public void Main () { // Binary Tree Node root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.right.left = new Node(16); root.right.right = new Node(19); LevelOrderTraversal(root); } } // This code is contributed by rag2127
Javascript
<script> // JavaScript program for the above approach class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to replace all nodes // at even and odd levels with their // nearest even or odd perfect squares function LevelOrderTraversal(root) { // Base Case if (root == null) return; // Create an empty queue // for level order traversal let q = []; // Enqueue root q.push(root); // Initialize height let lvl = 1; // Iterate until queue is not empty while (q.length != 0) { // Store the size // of the queue let n = q.length; // Traverse in range [1, n] for(let i = 0; i < n; i++) { // Store the current node let node = q[0]; // Store its square root let num = Math.sqrt(node.data); let x1 = Math.floor(num); let x2 = Math.ceil(num); // Check if it is a perfect square if (x1 == x2) { // If level is odd and value is even, // find the closest odd perfect square if (((lvl & 1) != 0) && !((x1 & 1) != 0)) { let num1 = x1 - 1, num2 = x1 + 1; node.data = (Math.abs(node.data - num1 * num1) < Math.abs(node.data - num2 * num2))? (num1 * num1) : (num2 * num2); } // If level is even and value is odd, // find the closest even perfect square if (!((lvl & 1) != 0) && ((x1 & 1) != 0)) { let num1 = x1 - 1, num2 = x1 + 1; node.data = (Math.abs(node.data - num1 * num1) < Math.abs(node.data - num2 * num2)) ? (num1 * num1) : (num2 * num2); } } // Otherwise, find the find // the nearest perfect square else { if ((lvl & 1) != 0) node.data = (x1 & 1) != 0 ? (x1 * x1) : (x2 * x2); else node.data = (x1 & 1) != 0 ? (x2 * x2) : (x1 * x1); } // Print front of queue // and remove it from queue document.write(node.data + " "); q.shift(); // Enqueue left child if (node.left != null) q.push(node.left); // Enqueue right child if (node.right != null) q.push(node.right); } // Increment the level by 1 lvl++; document.write("</br>"); } } // Binary Tree let root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.right.left = new Node(16); root.right.right = new Node(19); LevelOrderTraversal(root); </script>
9 4 4 9 25
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