Modifique el árbol binario reemplazando todos los Nodes en niveles pares e impares por sus cuadrados perfectos pares o impares más cercanos, respectivamente

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 19

Salida:        9
                  / \
                4 4
                      / \ 
                    9 25

Explicació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
                      /     
                    89    

Salida:       49
                  / \
                64 36
                      /    
                   81

Explicació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:

  1. Inicialice una cola , diga q. 
  2. Empuje la raíz en la cola.
  3. 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *