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
Á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