Compruebe si dos árboles binarios son espejo | conjunto 3

Dadas dos arrays , A[] y B[] que consisten en M pares , que representan los bordes de los dos árboles binarios de N Nodes distintos de acuerdo con el recorrido de orden de niveles , la tarea es verificar si los árboles son imágenes especulares entre sí.

Ejemplos:

Entrada: N = 6, M = 5, A[][2] = {{1, 5}, {1, 4}, {5, 7}, {5, 8}, {4, 9}}, B [][2] = {{1, 4}, {1, 5}, {4, 9}, {5, 8}, {5, 7}}
Salida: Sí
Explicación:

Ejemplo 1

Entrada: N = 5, M = 4, A[][2] = {{10, 20}, {10, 30}, {20, 40}, {20, 50}}, B[][2] = {{10, 30}, {10, 20}, {20, 40}, {20, 50}}
Salida: No
Explicación:

Ejemplo 2

El conjunto 1 y el conjunto 2 de este artículo se han discutido en artículos anteriores.

Enfoque: El problema dado se puede resolver usando estructuras de datos Map y Set . Siga los pasos a continuación para resolver el problema:

• Inicialice dos, los mapas de vectores dicen T1 y T2 para almacenar la lista de adyacencia de los árboles A y B respectivamente.
• Inicialice un conjunto, digamos St , para almacenar todos los valores de los Nodes únicos.
• Recorra el arreglo A[] usando la variable i, y realizando los siguientes pasos:
  • Inserte el valor A[i][1] en el vector T1[A[i][0]] y luego agregue A[i][0] y A[i][1] al conjunto St .
• Como los bordes se dan de acuerdo con el orden de nivel transversal , por lo tanto, en el árbol A para todos los Nodes, el hijo izquierdo se insertó primero y luego se insertó el hijo derecho.
• Recorra la array B[] en orden inverso usando la variable i y realizando los siguientes pasos:
  • Introduzca el valor B[i][1] en el vector T2[B[i][0]] y luego agregue B[i][0] y B[i][1] al conjunto St .
• Como la array B[] se recorre en sentido inverso, por lo tanto, en el árbol B para todos los Nodes, se insertó primero el elemento secundario derecho y luego se insertó el elemento secundario izquierdo.
• Ahora itere sobre el conjunto St y verifique si los vectores de los hijos del Node actual en el árbol A no son iguales a los vectores de los hijos del Node actual en el árbol B , luego imprima » No » como respuesta y luego regrese .
• Finalmente, si ninguno de los casos anteriores satisface, escriba » Sí » como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether two binary
// trees are mirror image of each other
// or not
string checkMirrorTree(int N, int M,
                       int A[][2], int B[][2])
{
    // Stores the adjacency list
    // of tree A
    map<int, vector<int> > T1;
 
    // Stores the adjacency list
    // of tree B
    map<int, vector<int> > T2;
 
    // Stores all distinct nodes
    set<int> st;
 
    // Traverse the array A[]
    for (int i = 0; i < M; i++) {
 
        // Push A[i][1] in the
        // vector T1[A[i][0]]
        T1[A[i][0]].push_back(A[i][1]);
 
        // Insert A[i][0] in the
        // set st
        st.insert(A[i][0]);
 
        // Insert A[i][1] in the
        // set st
        st.insert(A[i][1]);
    }
 
    // Traverse the array B[] in
    // reverse
    for (int i = M - 1; i >= 0; i--) {
 
        // Push B[i][1] in the
        // vector T2[B[i][0]]
        T2[B[i][0]].push_back(B[i][1]);
 
        // Insert B[i][0] in the
        // set st
        st.insert(B[i][0]);
 
        // Insert B[i][0] in the
        // set st
        st.insert(B[i][1]);
    }
 
    // Iterate over the set st
    for (auto node : st) {
 
        // If vector T1[node] is
        // not equals to T2[node]
        if (T1[node] != T2[node])
            return "No";
    }
 
    // Return "Yes" as
    // the answer
    return "Yes";
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 6;
    int M = 5;
 
    int A[][2] = {
        { 1, 5 }, { 1, 4 }, { 5, 7 }, { 5, 8 }, { 4, 9 }
    };
    int B[][2] = {
        { 1, 4 }, { 1, 5 }, { 4, 9 }, { 5, 8 }, { 5, 7 }
    };
 
    // Function Call
    cout << checkMirrorTree(N, M, A, B);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class Main
{
    // Function to check whether two binary
    // trees are mirror image of each other
    // or not
    static String checkMirrorTree(int N, int M, int[][] A, int[][] B)
    {
        
        // Stores the adjacency list
        // of tree A
        HashMap<Integer, Vector<Integer>> T1 = new HashMap<Integer, Vector<Integer>>();
       
        // Stores the adjacency list
        // of tree B
        HashMap<Integer, Vector<Integer>> T2 = new HashMap<Integer, Vector<Integer>>();
       
        // Stores all distinct nodes
        Set<Integer> st = new HashSet<Integer>();
       
        // Traverse the array A[]
        for (int i = 0; i < M; i++) {
       
            // Push A[i][1] in the
            // vector T1[A[i][0]]
            if(T1.containsKey(A[i][0]))
            {
                T1.get(A[i][0]).add(A[i][1]);
            }
            else{
                T1.put(A[i][0], new Vector<Integer>());
                T1.get(A[i][0]).add(A[i][1]);
            }
       
            // Insert A[i][0] in the
            // set st
            st.add(A[i][0]);
       
            // Insert A[i][1] in the
            // set st
            st.add(A[i][1]);
        }
       
        // Traverse the array B[] in
        // reverse
        for (int i = M - 1; i >= 0; i--) {
       
            // Push B[i][1] in the
            // vector T2[B[i][0]]
            if(T2.containsKey(B[i][0]))
            {
                T2.get(B[i][0]).add(B[i][1]);
            }
            else{
                T2.put(B[i][0], new Vector<Integer>());
                T2.get(B[i][0]).add(B[i][1]);
            }
       
            // Insert B[i][0] in the
            // set st
            st.add(B[i][0]);
       
            // Insert B[i][0] in the
            // set st
            st.add(B[i][1]);
        }
       
        // Iterate over the set st
        for(int node : st) {
       
            // If vector T1[node] is
            // not equals to T2[node]
            if (!(T1.get(node) == T2.get(node)))
                return "Yes";
        }
       
        // Return "No" as
        // the answer
        return "No";
    }
     
    public static void main(String[] args) {
        // Given Input
        int N = 6;
        int M = 5;
       
        int[][] A = {
            { 1, 5 }, { 1, 4 }, { 5, 7 }, { 5, 8 }, { 4, 9 }
        };
        int[][] B = {
            { 1, 4 }, { 1, 5 }, { 4, 9 }, { 5, 8 }, { 5, 7 }
        };
       
        // Function Call
        System.out.print(checkMirrorTree(N, M, A, B));
    }
}
 
// This code is contributed by rameshtravel07.

# Py program for the above approach
 
# Function to check whether two binary
# trees are mirror image of each other
# or not
def checkMirrorTree(N, M, A, B):
   
    # Stores the adjacency list
    # of tree A
    T1 = [[] for i in range(100)]
 
    # Stores the adjacency list
    # of tree B
    T2 = [[] for i in range(100)]
 
    # Stores all distinct nodes
    st = {}
 
    # Traverse the array A[]
    for i in range(M):
       
        # Push A[i][1] in the
        # vector T1[A[i][0]]
        T1[A[i][0]].append(A[i][1])
 
        # Insert A[i][0] in the
        # set st
        st[A[i][0]] = 1
 
        # Insert A[i][1] in the
        # set st
        st[A[i][1]] = 1
         
    # Traverse the array B[] in
    # reverse
    for i in range(M - 1, -1, -1):
        # Push B[i][1] in the
        # vector T2[B[i][0]]
        T2[B[i][0]].append(B[i][1])
 
        # Insert B[i][0] in the
        # set st
        st[B[i][0]] = 1
 
        # Insert B[i][0] in the
        # set st
        st[B[i][1]] = 1
 
    # Iterate over the set st
    for node in st:
 
        # If vector T1[node] is
        # not equals to T2[node]
        if (T1[node] != T2[node]):
            return "No"
 
    # Return "Yes" as
    # the answer
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
    # Given Input
    N = 6
    M = 5
 
    A =[ [1, 5], [1, 4], [5, 7], [5, 8], [4, 9]]
    B =[ [ 1, 4 ],[ 1, 5 ],[ 4, 9 ],[ 5, 8 ],[ 5, 7 ]]
 
    # Function Call
    print (checkMirrorTree(N, M, A, B))
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to check whether two binary
    // trees are mirror image of each other
    // or not
    static string checkMirrorTree(int N, int M,
                           int[,] A, int[,] B)
    {
       
        // Stores the adjacency list
        // of tree A
        Dictionary<int, List<int>> T1 = new Dictionary<int, List<int>>();
      
        // Stores the adjacency list
        // of tree B
        Dictionary<int, List<int>> T2 = new Dictionary<int, List<int>>();
      
        // Stores all distinct nodes
        HashSet<int> st = new HashSet<int>();
      
        // Traverse the array A[]
        for (int i = 0; i < M; i++) {
      
            // Push A[i][1] in the
            // vector T1[A[i][0]]
            if(T1.ContainsKey(A[i,0]))
            {
                T1[A[i,0]].Add(A[i,1]);
            }
            else{
                T1[A[i,0]] = new List<int>();
                T1[A[i,0]].Add(A[i,1]);
            }
      
            // Insert A[i][0] in the
            // set st
            st.Add(A[i,0]);
      
            // Insert A[i][1] in the
            // set st
            st.Add(A[i,1]);
        }
      
        // Traverse the array B[] in
        // reverse
        for (int i = M - 1; i >= 0; i--) {
      
            // Push B[i][1] in the
            // vector T2[B[i][0]]
            if(T2.ContainsKey(B[i,0]))
            {
                T2[B[i,0]].Add(B[i,1]);
            }
            else{
                T2[B[i,0]] = new List<int>();
                T2[B[i,0]].Add(B[i,1]);
            }
      
            // Insert B[i][0] in the
            // set st
            st.Add(B[i,0]);
      
            // Insert B[i][0] in the
            // set st
            st.Add(B[i,1]);
        }
      
        // Iterate over the set st
        foreach(int node in st) {
      
            // If vector T1[node] is
            // not equals to T2[node]
            if (!T1[node].Equals(T2[node]))
                return "Yes";
        }
      
        // Return "No" as
        // the answer
        return "No";
    }
 
  static void Main()
  {
     
    // Given Input
    int N = 6;
    int M = 5;
  
    int[,] A = {
        { 1, 5 }, { 1, 4 }, { 5, 7 }, { 5, 8 }, { 4, 9 }
    };
    int[,] B = {
        { 1, 4 }, { 1, 5 }, { 4, 9 }, { 5, 8 }, { 5, 7 }
    };
  
    // Function Call
    Console.Write(checkMirrorTree(N, M, A, B));
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for the above approach
     
    // Function to check whether two binary
    // trees are mirror image of each other
    // or not
    function checkMirrorTree(N, M, A, B)
    {
     
        // Stores the adjacency list
        // of tree A
        let T1 = [];
 
        // Stores the adjacency list
        // of tree B
        let T2 = [];
         
        for(let i = 0; i < 100; i++)
        {
            T1.push([]);
            T2.push([]);
        }
 
        // Stores all distinct nodes
        let st = new Map();
 
        // Traverse the array A[]
        for(let i = 0; i < M; i++)
        {
            // Push A[i][1] in the
            // vector T1[A[i][0]]
            T1[A[i][0]].push(A[i][1]);
 
            // Insert A[i][0] in the
            // set st
            st[A[i][0]] = 1;
 
            // Insert A[i][1] in the
            // set st
            st[A[i][1]] = 1;
        }
 
        // Traverse the array B[] in
        // reverse
        for(let i = M - 1; i < -1; i=-1)
        {
            // Push B[i][1] in the
            // vector T2[B[i][0]]
            T2[B[i][0]].push(B[i][1]);
 
            // Insert B[i][0] in the
            // set st
            st[B[i][0]] = 1;
 
            // Insert B[i][0] in the
            // set st
            st[B[i][1]] = 1;
        }
 
        // Iterate over the set st
        st.forEach((values,node)=>{
          // If vector T1[node] is
          // not equals to T2[node]
          if (T1[node] != T2[node])
          {
            return "No";
          }
        })
 
        // Return "Yes" as
        // the answer
        return "Yes";
    }
     
    // Given Input
    let N = 6;
    let M = 5;
  
    let A = [ [1, 5], [1, 4], [5, 7], [5, 8], [4, 9]];
    let B = [ [ 1, 4 ],[ 1, 5 ],[ 4, 9 ],[ 5, 8 ],[ 5, 7 ]];
  
    // Function Call
    document.write(checkMirrorTree(N, M, A, B));
     
    // This code is contributed by divyeshrabadiya07.
</script>

Yes

Complejidad de tiempo: O((N+M)*log(N))
Espacio auxiliar: O(N+M)