Dado un árbol binario, la tarea es verificar si el árbol binario contiene un subárbol duplicado de tamaño dos o más.
Input:
A
/ \
B C
/ \ \
D E B
/ \
D E
Output: Yes
B
/ \
D E
is the duplicate sub-tree.
Input:
A
/ \
B C
/ \
D E
Output: No
Enfoque: Aquí se ha discutido un enfoque basado en SFD . Se puede usar una cola para atravesar el árbol de manera bfs . Mientras atraviesa los Nodes, empuje el Node junto con sus hijos izquierdo y derecho en un mapa y si algún punto del mapa contiene duplicados, entonces el árbol contiene subárboles duplicados. Por ejemplo, si el Node es A y sus hijos son B y C, entonces ABC se insertará en el mapa. Si en algún momento se debe volver a presionar ABC, el árbol contiene subárboles duplicados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// 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;
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
bool dupSubUtil(Node* root)
{
// To store subtrees
set<string> subtrees;
// Used to traverse tree
queue<Node*> bfs;
bfs.push(root);
while (!bfs.empty()) {
Node* n = bfs.front();
bfs.pop();
// To store the left and the right
// children of the current node
char l = ' ', r = ' ';
// If the node has a left child
if (n->left != NULL) {
l = n->left->key;
// Push left node's data
bfs.push(n->left);
}
// If the node has a right child
if (n->right != NULL) {
r = n->right->key;
// Push right node's data
bfs.push(n->right);
}
string subt;
subt += n->key;
subt += l;
subt += r;
if (l != ' ' || r != ' ') {
// If this subtree count is greater than 0
// that means duplicate exists
if (!subtrees.insert(subt).second) {
return true;
}
}
}
return false;
}
// Driver code
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');
cout << (dupSubUtil(root) ? "Yes" : "No");
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Structure for a binary tree node
static class Node
{
char key;
Node left, right;
};
// A utility function to create a new node
static Node newNode(char key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return node;
}
static HashSet<String> subtrees = new HashSet<String>();
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
static boolean dupSubUtil(Node root)
{
// To store subtrees
// HashSet<String> subtrees;
// Used to traverse tree
Queue<Node> bfs = new LinkedList<>();
bfs.add(root);
while (!bfs.isEmpty())
{
Node n = bfs.peek();
bfs.remove();
// To store the left and the right
// children of the current node
char l = ' ', r = ' ';
// If the node has a left child
if (n.left != null)
{
l = n.left.key;
// Push left node's data
bfs.add(n.left);
}
// If the node has a right child
if (n.right != null)
{
r = n.right.key;
// Push right node's data
bfs.add(n.right);
}
String subt = "";
subt += n.key;
subt += l;
subt += r;
if (l != ' ' || r != ' ')
{
// If this subtree count is greater than 0
// that means duplicate exists
if (!subtrees.contains(subt))
{
return true;
}
}
}
return false;
}
// Driver code
public static void main(String[] args)
{
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');
if (dupSubUtil(root))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach
# Structure for a binary tree node
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.key = data
self.left = None
self.right = None
subtrees = set()
# Function that returns true if
# tree contains a duplicate subtree
# of size 2 or more
def dupSubUtil(root):
# To store subtrees
subtrees= set()
# Used to traverse tree
bfs = []
bfs.append(root)
while (len(bfs)):
n = bfs[0]
bfs.pop(0)
# To store the left and the right
# children of the current node
l = ' '
r = ' '
# If the node has a left child
if (n.left != None):
x = n.left
l = x.key
# append left node's data
bfs.append(n.left)
# If the node has a right child
if (n.right != None):
x = n.right
r = x.key
# append right node's data
bfs.append(n.right)
subt=""
subt += n.key
subt += l
subt += r
if (l != ' ' or r != ' '):
# If this subtree count is greater than 0
# that means duplicate exists
subtrees.add(subt)
if (len(subtrees) > 1):
return True
return False
# Driver code
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')
if dupSubUtil(root):
print("Yes")
else:
print("No")
# This code is contributed by SHUBHAMSINGH10
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Structure for a binary tree node
public class Node
{
public char key;
public Node left, right;
};
// A utility function to create a new node
static Node newNode(char key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return node;
}
static HashSet<String> subtrees = new HashSet<String>();
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
static bool dupSubUtil(Node root)
{
// To store subtrees
// HashSet<String> subtrees;
// Used to traverse tree
Queue<Node> bfs = new Queue<Node>();
bfs.Enqueue(root);
while (bfs.Count != 0)
{
Node n = bfs.Peek();
bfs.Dequeue();
// To store the left and the right
// children of the current node
char l = ' ', r = ' ';
// If the node has a left child
if (n.left != null)
{
l = n.left.key;
// Push left node's data
bfs.Enqueue(n.left);
}
// If the node has a right child
if (n.right != null)
{
r = n.right.key;
// Push right node's data
bfs.Enqueue(n.right);
}
String subt = "";
subt += n.key;
subt += l;
subt += r;
if (l != ' ' || r != ' ')
{
// If this subtree count is greater than 0
// that means duplicate exists
if (!subtrees.Contains(subt))
{
return true;
}
}
}
return false;
}
// Driver code
public static void Main(String[] args)
{
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');
if (dupSubUtil(root))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Structure for a binary tree node
class Node
{
constructor()
{
this.key = '';
this.left = null;
this.right = null;
}
};
// A utility function to create a new node
function newNode(key)
{
var node = new Node();
node.key = key;
node.left = node.right = null;
return node;
}
var subtrees = new Set();
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
function dupSubUtil(root)
{
// To store subtrees
// HashSet<String> subtrees;
// Used to traverse tree
var bfs = [];
bfs.push(root);
while (bfs.length != 0)
{
var n = bfs[0];
bfs.pop();
// To store the left and the right
// children of the current node
var l = ' ', r = ' ';
// If the node has a left child
if (n.left != null)
{
l = n.left.key;
// Push left node's data
bfs.push(n.left);
}
// If the node has a right child
if (n.right != null)
{
r = n.right.key;
// Push right node's data
bfs.push(n.right);
}
var subt = "";
subt += n.key;
subt += l;
subt += r;
if (l != ' ' || r != ' ')
{
// If this subtree count is greater than 0
// that means duplicate exists
if (!subtrees.has(subt))
{
return true;
}
}
}
return false;
}
// Driver code
var 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');
if (dupSubUtil(root))
document.write("Yes");
else
document.write("No");
// This code is contributed by rrrtnx.
</script>
Producción:
Yes
Complejidad de tiempo : O (n) donde N es no de Nodes en un árbol binario
Espacio Auxiliar: O(n)