Compruebe si un árbol binario contiene subárboles duplicados de tamaño 2 o más

Dado un árbol binario, compruebe si el árbol binario contiene un subárbol duplicado de tamaño 2 o más. 
Nota: dos Nodes de hoja iguales no se consideran como tamaño de subárbol de un Node de hoja es uno.

Input :  Binary Tree 
               A
             /    \ 
           B        C
         /   \       \    
        D     E       B     
                     /  \    
                    D    E
Output : Yes

Preguntado en: Entrevista de Google 

Tree

Árbol con subárbol duplicado [resaltado con elipse de color azul]

[Método 1] 
Una solución simple es que seleccionamos cada Node del árbol e intentamos encontrar si algún subárbol de un árbol dado está presente en el árbol que es idéntico a ese subárbol. Aquí podemos usar la publicación a continuación para encontrar si un subárbol está presente en cualquier otro lugar del árbol. 
Comprobar si un árbol binario es un subárbol de otro árbol binario 

[Método 2] (solución eficiente) 
Una solución eficiente basada en la serialización de árboles y hashing . La idea es serializar subárboles como strings y almacenar las strings en una tabla hash. Una vez que encontramos un árbol serializado (que no es una hoja) que ya existe en la tabla hash, devolvemos verdadero. 

Abajo La implementación de la idea anterior. 

C++

// C++ program to find if there is a duplicate
// sub-tree of size 2 or more.
#include<bits/stdc++.h>
using namespace std;
 
// Separator node
const char MARKER = '$';
 
// Structure for a binary tree node
struct Node
{
    char key;
    Node *left, *right;
};
 
// A utility function to create a new node
Node* newNode(char key)
{
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
 
unordered_set<string> subtrees;
 
// This function returns empty string if tree
// contains a duplicate subtree of size 2 or more.
string dupSubUtil(Node *root)
{
    string s = "";
 
    // If current node is NULL, return marker
    if (root == NULL)
        return s + MARKER;
 
    // If left subtree has a duplicate subtree.
    string lStr = dupSubUtil(root->left);
    if (lStr.compare(s) == 0)
    return s;
 
    // Do same for right subtree
    string rStr = dupSubUtil(root->right);
    if (rStr.compare(s) == 0)
    return s;
 
    // Serialize current subtree
    s = s + root->key + lStr + rStr;
 
    // If current subtree already exists in hash
    // table. [Note that size of a serialized tree
    // with single node is 3 as it has two marker
    // nodes.
    if (s.length() > 3 &&
        subtrees.find(s) != subtrees.end())
    return "";
 
    subtrees.insert(s);
 
    return s;
}
 
// Driver program to test above functions
int main()
{
    Node *root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('C');
    root->left->left = newNode('D');
    root->left->right = newNode('E');
    root->right->right = newNode('B');
    root->right->right->right = newNode('E');
    root->right->right->left= newNode('D');
 
    string str = dupSubUtil(root);
 
    (str.compare("") == 0) ? cout << " Yes ":
                            cout << " No " ;
    return 0;
}

Java

// Java program to find if there is a duplicate
// sub-tree of size 2 or more.
import java.util.HashSet;
public class Main {
 
    static char MARKER = '$';
 
    // This function returns empty string if tree
    // contains a duplicate subtree of size 2 or more.
    public static String dupSubUtil(Node root, HashSet<String> subtrees)
    {
        String s = "";
     
        // If current node is NULL, return marker
        if (root == null)
            return s + MARKER;
     
        // If left subtree has a duplicate subtree.
        String lStr = dupSubUtil(root.left,subtrees);
        if (lStr.equals(s))
            return s;
     
        // Do same for right subtree
        String rStr = dupSubUtil(root.right,subtrees);
        if (rStr.equals(s))
            return s;
     
        // Serialize current subtree
        s = s + root.data + lStr + rStr;
     
        // If current subtree already exists in hash
        // table. [Note that size of a serialized tree
        // with single node is 3 as it has two marker
        // nodes.
        if (s.length() > 3 && subtrees.contains(s))
            return "";
     
        subtrees.add(s);
        return s;
    }
 
    //Function to find if the Binary Tree contains duplicate
    //subtrees of size 2 or more
    public static String dupSub(Node root)
    {
        HashSet<String> subtrees=new HashSet<>();
        return dupSubUtil(root,subtrees);
    }
 
    public static void main(String args[])
    {
        Node root = new Node('A');
        root.left = new Node('B');
        root.right = new Node('C');
        root.left.left = new Node('D');
        root.left.right = new Node('E');
        root.right.right = new Node('B');
        root.right.right.right = new Node('E');
        root.right.right.left= new Node('D');
        String str = dupSub(root);
        if(str.equals(""))
            System.out.print(" Yes ");
        else   
            System.out.print(" No ");
    }
}
 
// A binary tree Node has data,
// pointer to left child
// and a pointer to right child
class Node {
    int data;
    Node left,right;
    Node(int data)
    {
        this.data=data;
    }
};
//This code is contributed by Gaurav Tiwari

Python3

# Python3 program to find if there is
# a duplicate sub-tree of size 2 or more
 
# Separator node
MARKER = '$'
 
# Structure for a binary tree node
class Node:
     
    def __init__(self, x):
         
        self.key = x
        self.left = None
        self.right = None
 
subtrees = {}
 
# This function returns empty if tree
# contains a duplicate subtree of size
# 2 or more.
def dupSubUtil(root):
     
    global subtrees
 
    s = ""
 
    # If current node is None, return marker
    if (root == None):
        return s + MARKER
 
    # If left subtree has a duplicate subtree.
    lStr = dupSubUtil(root.left)
     
    if (s in lStr):
       return s
 
    # Do same for right subtree
    rStr = dupSubUtil(root.right)
     
    if (s in rStr):
       return s
 
    # Serialize current subtree
    s = s + root.key + lStr + rStr
 
    # If current subtree already exists in hash
    # table. [Note that size of a serialized tree
    # with single node is 3 as it has two marker
    # nodes.
    if (len(s) > 3 and s in subtrees):
       return ""
 
    subtrees[s] = 1
 
    return s
 
# Driver code
if __name__ == '__main__':
     
    root = Node('A')
    root.left = Node('B')
    root.right = Node('C')
    root.left.left = Node('D')
    root.left.right = Node('E')
    root.right.right = Node('B')
    root.right.right.right = Node('E')
    root.right.right.left= Node('D')
 
    str = dupSubUtil(root)
 
    if "" in str:
        print(" Yes ")
    else:
        print(" No ")
 
# This code is contributed by mohit kumar 29

C#

// C# program to find if there is a duplicate
// sub-tree of size 2 or more.
using System;
using System.Collections.Generic;
 
class GFG
{
 
    static char MARKER = '$';
 
    // This function returns empty string if tree
    // contains a duplicate subtree of size 2 or more.
    public static String dupSubUtil(Node root,
                    HashSet<String> subtrees)
    {
        String s = "";
     
        // If current node is NULL, return marker
        if (root == null)
            return s + MARKER;
     
        // If left subtree has a duplicate subtree.
        String lStr = dupSubUtil(root.left,subtrees);
        if (lStr.Equals(s))
            return s;
     
        // Do same for right subtree
        String rStr = dupSubUtil(root.right,subtrees);
        if (rStr.Equals(s))
            return s;
     
        // Serialize current subtree
        s = s + root.data + lStr + rStr;
     
        // If current subtree already exists in hash
        // table. [Note that size of a serialized tree
        // with single node is 3 as it has two marker
        // nodes.
        if (s.Length > 3 && subtrees.Contains(s))
            return "";
     
        subtrees.Add(s);
        return s;
    }
 
    // Function to find if the Binary Tree contains
    // duplicate subtrees of size 2 or more
    public static String dupSub(Node root)
    {
        HashSet<String> subtrees = new HashSet<String>();
        return dupSubUtil(root,subtrees);
    }
 
    // Driver code
    public static void Main(String []args)
    {
        Node root = new Node('A');
        root.left = new Node('B');
        root.right = new Node('C');
        root.left.left = new Node('D');
        root.left.right = new Node('E');
        root.right.right = new Node('B');
        root.right.right.right = new Node('E');
        root.right.right.left= new Node('D');
        String str = dupSub(root);
        if(str.Equals(""))
            Console.Write(" Yes ");
        else
            Console.Write(" No ");
    }
}
 
// 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,right;
    public Node(int data)
    {
        this.data = data;
    }
};
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program to find if there is a duplicate
// sub-tree of size 2 or more.
     
    let MARKER = '$';
     
    // A binary tree Node has data,
// pointer to left child
// and a pointer to right child
    class Node {
        constructor(data)
        {
            this.data=data;
        }
    }
     
    // This function returns empty string if tree
    // contains a duplicate subtree of size 2 or more.
    function dupSubUtil(root,subtrees)
    {
        let s = "";
      
        // If current node is NULL, return marker
        if (root == null)
            return s + MARKER;
      
        // If left subtree has a duplicate subtree.
        let lStr = dupSubUtil(root.left,subtrees);
        if (lStr==(s))
            return s;
      
        // Do same for right subtree
        let rStr = dupSubUtil(root.right,subtrees);
        if (rStr==(s))
            return s;
      
        // Serialize current subtree
        s = s + root.data + lStr + rStr;
      
        // If current subtree already exists in hash
        // table. [Note that size of a serialized tree
        // with single node is 3 as it has two marker
        // nodes.
        if (s.length > 3 && subtrees.has(s))
            return "";
      
        subtrees.add(s);
        return s;
    }
     
    //Function to find if the Binary Tree contains duplicate
    //subtrees of size 2 or more
    function dupSub(root)
    {
            let subtrees=new Set();
             
            return dupSubUtil(root,subtrees);
    }
     
    let root = new Node('A');
    root.left = new Node('B');
    root.right = new Node('C');
    root.left.left = new Node('D');
    root.left.right = new Node('E');
    root.right.right = new Node('B');
    root.right.right.right = new Node('E');
    root.right.right.left= new Node('D');
    let str = dupSub(root);
    if(str==(""))
        document.write(" Yes ");
     else  
        document.write(" No ");
     
 
// This code is contributed by unknown2108
</script>

Producción: 

Yes

Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

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