Compruebe si dos árboles binarios son idénticos después de exactamente K cambios

Posted on by Rudeus Greyrat

Dados dos árboles binarios T1 y T2 y el número entero K , la tarea es verificar si ambos árboles son idénticos o no después de hacer exactamente K cambios en el primer árbol. En cada cambio, un elemento del árbol se puede convertir en cualquier otro entero.

Ejemplos:  

 Entrada: K = 1
 T1 = 1 T2 = 1
        / \ / \
      2 4 2 3
Salida: Sí
Explicación: Cambiar el Node con valor 4 a valor 3

Entrada: K = 5
T1 = 1 T2 = 1
         / \ / \
     2 5 3 5
  / \ / \ / \ / \
7 9 10 11 7 6 10 21

Salida: Sí
Explicación: En los dos árboles anteriores hay 3 valores de Node que son diferentes en el primer árbol, es decir, 2, 9, 11.
Por lo tanto, hacemos al menos 3 cambios para convertirlos en 3, 6, 21 respectivamente para que el árbol sea idéntico. 
Después de 3 cambios dejó K = 5 – 3 = 2 cambios. 
Utilice estos dos cambios convirtiendo cualquier Node en uno aleatorio y luego vuelva a convertirlo en el original. 
De esta forma tenemos exactamente K = 5 cambios.

 

Enfoque: El problema se resuelve usando un enfoque iterativo usando una pila.

  • Verificamos todos los Nodes respectivos de ambos árboles uno por uno con la ayuda del recorrido iterativo en orden .
  • Si descubrimos que las partes de datos respectivas de ambos árboles no coinciden, simplemente incrementamos el conteo.
  • Si la estructura de ambos árboles es diferente, devuelve false.
  • Al final, verificamos si nuestro conteo es menor que K y (k-conteo) es par o no, si es así, devuelve verdadero; de lo contrario, devuelve falso.

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

C++

// C++ code to implement the 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;
};
 
// Function to create new node.
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return (Node);
}
 
// Given two trees, return
// true if they are
// convertible to identical
bool checkIdentical(node* p, node* q, int k)
{
    stack<node *> st1, st2;
    int count = 0;
 
    while (p || !st1.empty() && q || !st2.empty()) {
 
        // If p are 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;
        }
 
        // when one of them is null means
        // they have different
        // structure return false
        else if (p && !q || !p && q)
            return 0;
 
        // 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;
        }
    }
 
    if (count <= k && (k - count) % 2 == 0)
        return 1;
    else
        return 0;
}
 
// Driver code
int main()
{
    /*    1           1
        /   \       /   \
       2     4     2     3
    */
 
    node* root1 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(4);
 
    node* root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
 
    int K = 1;
    if (checkIdentical(root1, root2, K))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java code to implement the above approach
 
 
import java.util.*;
 
class GFG{
 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
static class node {
    int data;
    node left;
    node right;
};
 
// Function to create new node.
static node newNode(int data)
{
    node Node = new node();
    Node.data = data;
    Node.left = null;
    Node.right = null;
 
    return (Node);
}
 
// Given two trees, return
// true if they are
// convertible to identical
static boolean checkIdentical(node p, node q, int k)
{
    Stack<node > st1 = new Stack<>();
    Stack<node > st2 = new Stack<>();
    int count = 0;
 
    while (p!=null || (st1.isEmpty()) && q!=null || !st2.isEmpty()) {
 
        // If p are q are not null
        // push in stack
        if (p!=null && q!=null) {
            st1.add(p);
            st2.add(q);
 
            // Send p and q to its left child
            p = p.left;
            q = q.left;
        }
 
        // when one of them is null means
        // they have different
        // structure return false
        else if (p!=null && q==null || p==null && q!=null)
        return false;
 
        // 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;
        }
    }
 
    if (count <= k && (k - count) % 2 == 0)
        return true;
    else
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    /*    1           1
        /   \       /   \
       2     4     2     3
    */
 
    node root1 = newNode(1);
    root1.left = newNode(2);
    root1.right = newNode(4);
 
    node root2 = newNode(1);
    root2.left = newNode(2);
    root2.right = newNode(3);
 
    int K = 1;
    if (checkIdentical(root1, root2, K))
        System.out.print("Yes");
    else
        System.out.print("No");
 
}
}
 
// This code contributed by shikhasingrajput

Python3

# Python code for the above approach
 
## A binary tree node has data,
## pointer to left child
## and a pointer to right child
class node:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None
             
## Function to create new node.
def newNode(data):
    Node = node(data);
    Node.left = None;
    Node.right = None;
 
    return Node
 
## Given two trees, return
## true if they are
## convertible to identical
def checkIdentical(p, q, k):
    st1 = []
    st2 = []
    count = 0
 
    while (p or (len(st1) > 0) and q or (len(st2) > 0)):
 
        ## If p are q are not null
        ## push in stack
        if (p and q):
            st1.append(p)
            st2.append(q)
 
            ## Send p and q to its left child
            p = p.left
            q = q.left
 
        ## when one of them is null means
        ## they have different
        ## structure return false
        elif (p and (not q) or (not p) and q):
            return 0
 
        ## If p and q are null
        ## pop node from stack
        else:
            p = st1.pop()
            st1.append(p)
            q = st2.pop()
            st2.append(q)
 
            st1.pop()
            st2.pop()
 
            ## If data not match increment count
            if (p.data != q.data):
                count+=1
 
            ## Send p and q to its right child
            p = p.right
            q = q.right
 
    if (count <= k and (k - count) % 2 == 0):
        return 1
    else:
        return 0
 
 
# Driver Code
if __name__=='__main__':
 
    ##   1       1
    ##    / \      / \
    ##  2 4     2  3
 
    root1 = newNode(1);
    root1.left = newNode(2);
    root1.right = newNode(4);
 
    root2 = newNode(1);
    root2.left = newNode(2);
    root2.right = newNode(3);
 
    K = 1;
    if (checkIdentical(root1, root2, K)):
        print("Yes")
    else:
        print("No")
 
        # This code is contributed by subhamgoyal2014.

C#

// C# code to implement 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;
    };
 
  // Function to create new node.
  static node newNode(int data)
  {
    node Node = new node();
    Node.data = data;
    Node.left = null;
    Node.right = null;
 
    return (Node);
  }
 
  // Given two trees, return
  // true if they are
  // convertible to identical
  static bool checkIdentical(node p, node q, int k)
  {
    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 are 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;
      }
 
      // when one of them is null means
      // they have different
      // structure return false
      else if (p!=null && q==null || p==null && q!=null)
        return false;
 
      // 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;
      }
    }
 
    if (count <= k && (k - count) % 2 == 0)
      return true;
    else
      return false;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    /*    1           1
        /   \       /   \
       2     4     2     3
    */
 
    node root1 = newNode(1);
    root1.left = newNode(2);
    root1.right = newNode(4);
 
    node root2 = newNode(1);
    root2.left = newNode(2);
    root2.right = newNode(3);
 
    int K = 1;
    if (checkIdentical(root1, root2, K))
      Console.Write("Yes");
    else
      Console.Write("No");
 
  }
}
 
// This code contributed by shikhasingrajput
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 *