Verifique si los árboles dados se pueden hacer imágenes especulares entre sí en intercambios K

Dados dos árboles binarios con la misma estructura pero que pueden tener diferente disposición de valor y dado un número entero K . La tarea es verificar que después de exactamente el intercambio de K en el primer árbol, se convertirá en un espejo del segundo. En un intercambio, tomamos dos Nodes del mismo padre e intercambiamos su subárbol izquierdo y derecho.

Ejemplos: 

Entrada:  K = 1
         1 1
       / \ / \
      2 3 2 3
Salida:

Entrada: K = 4
           11 11
     / \ / \
   25 15 25 15
 / \ / \ / \ / \
7 9 10 21 10 21 9 7
Salida: 
Explicación: Aquí primero necesitamos intercambiar dos pares (25, 15) y (10, 21) en el primer árbol, por lo tanto, K = 2. Y luego intercambiamos (21, 7) y (10, 9), por lo tanto, aquí hay un total de 4 intercambios.

Enfoque: El enfoque básico para resolver este problema es usar la recursividad y la pila según la siguiente idea:

La idea es atravesar el primer árbol y verificar intercambiando Nodes recursivamente , si el árbol se convierte en una imagen especular del segundo árbol.  

Siga los pasos a continuación para implementar el enfoque anterior:

  • Verifique todos los Nodes respectivos de ambos árboles uno por uno con la ayuda del recorrido iterativo en orden .
  • Si se encuentra que las partes de datos respectivas de ambos árboles no coinciden, simplemente incrementamos la cantidad de intercambios necesarios 
  • Una vez que se complete el recorrido, verifique la condición a continuación y devuelva Sí si alguna de las condiciones a continuación es verdadera: 
    • si nuestro conteo es igual a K, 
    • si cuenta es menor que K y (K – cuenta) es par,
  •  De lo contrario, devuelva No.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class node {
   
public:
    int data;
    node* left;
    node* right;
};
 
// Create new node.
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return (Node);
}
 
// Function to convert tree
// into its mirror tree
void convert(node* root)
{
 
    if (!root)
        return;
 
    // Recursively call left
    // and right node
    convert(root->left);
    convert(root->right);
 
    // Swap left and right of any node
    swap(root->left, root->right);
}
 
// Function to check identical and
// count no of swap needed to be
int checkIdentical(node* p, node* q)
{
    stack<node*> st1, st2;
    int count = 0;
 
    while (p || !st1.empty()
           && q || !st2.empty()) {
 
        // If p q are not
        // null push in stack
        if (p && q) {
            st1.push(p);
            st2.push(q);
 
            // Send p and q
            // to its left child
            p = p->left;
            q = q->left;
        }
 
        // If p and q are null
        // pop node from stack
        else {
            p = st1.top();
            q = st2.top();
 
            st1.pop();
            st2.pop();
 
            // If data not match
            // increment count
            if (p->data != q->data)
                count++;
 
            // Send p and q to
            // its right child
            p = p->right;
            q = q->right;
        }
    }
 
    // Return count/2 because
    // we swap pairs
    return count / 2;
}
 
/* Driver code*/
int main()
{
 
    node* root1 = newNode(11);
    root1->left = newNode(25);
    root1->right = newNode(15);
    root1->left->left = newNode(7);
    root1->left->right = newNode(9);
    root1->right->left = newNode(10);
    root1->right->right = newNode(21);
 
    node* root2 = newNode(11);
    root2->left = newNode(25);
    root2->right = newNode(15);
    root2->left->left = newNode(10);
    root2->left->right = newNode(21);
    root2->right->left = newNode(9);
    root2->right->right = newNode(7);
 
    int K = 4;
 
    // First convert first
    // tree into mirror tree
    convert(root1);
 
    int count = checkIdentical(root1, root2);
 
    if (count <= K
        && (K - count) % 2 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
 
    return 0;
}

Java

// Java code for the above approach:
import java.util.*;
 
class GFG
{
 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
 
  public static class node {
    int data;
    node left;
    node right;
    
  }
 
// Create new node.
public static node newNode(int data)
{
    node Node = new node();
    Node.data = data;
    Node.left = null;
    Node.right = null;
 
    return (Node);
}
 
// Swapping the node
static void swap(node m, node n)
{
    // Swapping the values
    node temp = m;
    m = n;
    n = temp;
         
}
 
// Function to convert tree
// into its mirror tree
public static void convert(node root)
{
 
    if (root==null)
        return;
 
    // Recursively call left
    // and right node
    convert(root.left);
    convert(root.right);
 
    // Swap left and right of any node
    swap(root.left, root.right);
}
 
// Function to check identical and
// count no of swap needed to be
public static int checkIdentical(node p, node q)
{
    Stack<node> st1=new Stack<>();
    Stack<node> st2=new Stack<>();
     
    int count = 0;
 
    while (p!=null || !st1.empty()
           && q!=null || !st2.empty()) {
 
        // If p q are not
        // null push in stack
        if (p!=null && q!=null) {
            st1.push(p);
            st2.push(q);
 
            // Send p and q
            // to its left child
            p = p.left;
            q = q.left;
        }
 
        // If p and q are null
        // pop node from stack
        else {
            p = st1.peek();
            q = st2.peek();
 
            st1.pop();
            st2.pop();
 
            // If data not match
            // increment count
            if (p.data != q.data)
                count++;
 
            // Send p and q to
            // its right child
            p = p.right;
            q = q.right;
        }
    }
 
    // Return count/2 because
    // we swap pairs
    return count / 2;
}
 
 
  // Driver Code
  public static void main(String[] args)
  {
    node root1 = newNode(11);
    root1.left = newNode(25);
    root1.right = newNode(15);
    root1.left.left = newNode(7);
    root1.left.right = newNode(9);
    root1.right.left = newNode(10);
    root1.right.right = newNode(21);
 
    node root2 = newNode(11);
    root2.left = newNode(25);
    root2.right = newNode(15);
    root2.left.left = newNode(10);
    root2.left.right = newNode(21);
    root2.right.left = newNode(9);
    root2.right.right = newNode(7);
 
    int K = 4;
 
    // First convert first
    // tree into mirror tree
    convert(root1);
 
    int count = checkIdentical(root1, root2);
 
    if (count <= K
        && (K - count) % 2 == 0)
        System.out.println("Yes");
    else
        System.out.println("No");
 
  }
}
 
// Tthis code is contributed by jana_sayantan.

Python3

# Python code for the above approach
 
# Node Class
class Node:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None
             
 
class LinkedList:
    def __init__(self):
        self.head = None
             
## Function to convert tree
## into its mirror tree
def convert(head):
    if(head == None):
        return
 
    ## Recursively call left
    ## and right node
    convert(head.left)
    convert(head.right)
 
    ## Swap left and right of any node
    head.left, head.right = head.right, head.left
 
## Function to check identical and
## count no of swap needed to be
def checkIdentical(head1, head2):
    st1 = []
    st2 = []
 
    count = 0
 
    while ( (head1!=None) or (len(st1)!=0)) and ( (head2!=None) or (len(st2)!=0)):
         
        ## If head1 head2 are not
        ## none push in stack
        if ((head1!=None) and (head2!=None)):
            st1.append(head1)
            st2.append(head2)
 
            ## Send head1 and head2
            ## to its left child
            head1 = head1.left
            head2 = head2.left
 
        ## If head1 and head2 are null
        ## pop node from stack
        else:
            head1 = st1[-1]
            head2 = st2[-1]
 
            st1.pop()
            st2.pop()
 
            ## If data not match
            ## increment count
            if (head1.data != head2.data):
                count+=1
 
            ## Send head1 and head2 to
            ## its right child
            head1 = head1.right
            head2 = head2.right
 
    ## Return count/2 because
    ## we swap pairs
    return count / 2
 
# Driver Code
if __name__=='__main__':
 
    llist1 = LinkedList()
    llist1.head = Node(11)
    llist1.head.left = Node(25)
    llist1.head.right = Node(15)
    llist1.head.left.left = Node(7)
    llist1.head.left.right = Node(9)
    llist1.head.right.left = Node(10)
    llist1.head.right.right = Node(21)
 
    llist2 = LinkedList()
    llist2.head = Node(11)
    llist2.head.left = Node(25)
    llist2.head.right = Node(15)
    llist2.head.left.left = Node(10)
    llist2.head.left.right = Node(21)
    llist2.head.right.left = Node(9)
    llist2.head.right.right = Node(7)
 
    K = 4
 
    ## First convert first
    ## tree into mirror tree
    convert(llist1.head)
 
    count = checkIdentical(llist1.head, llist2.head)
 
    if (count <= K and (K - count) % 2 == 0):
        print("Yes")
    else:
        print("No")
 
        # This code is contributed by subhamgoyal2014.

C#

// C# code for the above approach:
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
 
  public class node {
    public int data;
    public node left;
    public node right;
    
  }
 
// Create new node.
public static node newNode(int data)
{
    node Node = new node();
    Node.data = data;
    Node.left = null;
    Node.right = null;
 
    return (Node);
}
 
// Swapping the node
static void swap(node m, node n)
{
    // Swapping the values
    node temp = m;
    m = n;
    n = temp;
         
}
 
// Function to convert tree
// into its mirror tree
public static void convert(node root)
{
 
    if (root==null)
        return;
 
    // Recursively call left
    // and right node
    convert(root.left);
    convert(root.right);
 
    // Swap left and right of any node
    swap(root.left, root.right);
}
 
// Function to check identical and
// count no of swap needed to be
public static int checkIdentical(node p, node q)
{
    Stack<node> st1=new Stack<node>();
    Stack<node> st2=new Stack<node>();
     
    int count = 0;
 
    while (p!=null || st1.Count!=0
           && q!=null || st2.Count!=0) {
 
        // If p q are not
        // null push in stack
        if (p!=null && q!=null) {
            st1.Push(p);
            st2.Push(q);
 
            // Send p and q
            // to its left child
            p = p.left;
            q = q.left;
        }
 
        // If p and q are null
        // pop node from stack
        else {
            p = st1.Peek();
            q = st2.Peek();
 
            st1.Pop();
            st2.Pop();
 
            // If data not match
            // increment count
            if (p.data != q.data)
                count++;
 
            // Send p and q to
            // its right child
            p = p.right;
            q = q.right;
        }
    }
 
    // Return count/2 because
    // we swap pairs
    return count / 2;
}
 
 
  // Driver Code
  public static void Main(String[] args)
  {
    node root1 = newNode(11);
    root1.left = newNode(25);
    root1.right = newNode(15);
    root1.left.left = newNode(7);
    root1.left.right = newNode(9);
    root1.right.left = newNode(10);
    root1.right.right = newNode(21);
 
    node root2 = newNode(11);
    root2.left = newNode(25);
    root2.right = newNode(15);
    root2.left.left = newNode(10);
    root2.left.right = newNode(21);
    root2.right.left = newNode(9);
    root2.right.right = newNode(7);
 
    int K = 4;
 
    // First convert first
    // tree into mirror tree
    convert(root1);
 
    int count = checkIdentical(root1, root2);
 
    if (count <= K
        && (K - count) % 2 == 0)
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
 
  }
}
 
 
// This code contributed by shikhasingrajput

Javascript

// Javascript program for the above approach
 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class node
{
 
  // Creates new node
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
 
// Swapping the node
function swap(m, n) {
  // Swapping the values
  let temp = m;
  m = n;
  n = temp;
}
 
// Function to convert tree
// into its mirror tree
function convert(root) {
  if (root == null) {
    return;
  }
 
  // Recursively call left and right node
  convert(root.left);
  convert(root.right);
 
  // Swap left and right of any node
  swap(root.left, root.right);
}
 
// Function to check identical and
// count no of swap needed to be
function checkIdentical(p, q) {
  let st1 = [];
  let st2 = [];
 
  let count = 0;
 
  while (p || st1.length || q || st2.length) {
    // If p q are not
    // null push in stack
    if (p && q) {
      st1.push(p);
      st2.push(q);
 
      // Send p and q
      // to its left child
      p = p.left;
      q = q.left;
    } else {
      p = st1[st1.length - 1];
      q = st2[st2.length - 1];
 
      st1.pop();
      st2.pop();
 
      // If data not match
      // increment count
      if (p.data != q.data) count++;
 
      // Send p and q to
      // its right child
      p = p.right;
      q = q.right;
    }
  }
  // Return count/2 because
  // we swap pairs
  return count / 2;
}
 
// Driver code
let root1 = new node(11);
root1.left = new node(25);
root1.right = new node(15);
root1.left.left = new node(7);
root1.left.right = new node(9);
root1.right.left = new node(10);
root1.right.right = new node(21);
 
let root2 = new node(11);
root2.left = new node(25);
root2.right = new node(15);
root2.left.left = new node(10);
root2.left.right = new node(21);
root2.right.left = new node(9);
root2.right.right = new node(7);
 
let k = 4;
 
// First convert first
// tree into mirror tree
convert(root1);
 
let count = checkIdentical(root1,root2);
 
if(count <= k && ((k - count) % 2) == 0){
    console.log("Yes");
}else{
    console.log("No");
}
 
// This code is contributed by Ishan Khandelwal
Producción

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por nobita04 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 *