Dado un árbol binario, encuentre todos los subárboles duplicados. Para cada subárbol duplicado, solo necesitamos devolver el Node raíz de cualquiera de ellos. Dos árboles son duplicados si tienen la misma estructura con los mismos valores de Node.
Ejemplos:
Input :
1
/ \
2 3
/ / \
4 2 4
/
4
Output :
2
/ and 4
4
Explanation: Above Trees are two duplicate subtrees.
Therefore, you need to return above trees root in the
form of a list.
La idea es usar hash . Almacenamos recorridos en orden de subárboles en un hash. Dado que el recorrido en orden simple no puede identificar de forma única un árbol, usamos símbolos como ‘(‘ y ‘)’ para representar Nodes NULL.
Pasamos un mapa desordenado en C++ como argumento a la función auxiliar que calcula recursivamente la string en orden y aumenta su conteo en el mapa. Si alguna string se repite, implicará la duplicación del subárbol enraizado en ese Node, así que inserte ese Node en el resultado final y devuelva el vector de estos Nodes.
Implementación:
C++
// C++ program to find averages of all levels
// in a binary tree.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int data;
struct Node* left, *right;
};
string inorder(Node* node, unordered_map<string, int>& m)
{
if (!node)
return "";
string str = "(";
str += inorder(node->left, m);
str += to_string(node->data);
str += inorder(node->right, m);
str += ")";
// Subtree already present (Note that we use
// unordered_map instead of unordered_set
// because we want to print multiple duplicates
// only once, consider example of 4 in above
// subtree, it should be printed only once.
if (m[str] == 1)
cout << node->data << " ";
m[str]++;
return str;
}
// Wrapper over inorder()
void printAllDups(Node* root)
{
unordered_map<string, int> m;
inorder(root, m);
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver code
int main()
{
Node* root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(2);
root->right->left->left = newNode(4);
root->right->right = newNode(4);
printAllDups(root);
return 0;
}
Java
// A java program to find all duplicate subtrees
// in a binary tree.
import java.util.HashMap;
public class Duplicate_subtress {
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static HashMap<String, Integer> m;
static class Node {
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left = null;
right = null;
}
}
static String inorder(Node node)
{
if (node == null)
return "";
String str = "(";
str += inorder(node.left);
str += Integer.toString(node.data);
str += inorder(node.right);
str += ")";
// Subtree already present (Note that we use
// HashMap instead of HashSet
// because we want to print multiple duplicates
// only once, consider example of 4 in above
// subtree, it should be printed only once.
if (m.get(str) != null && m.get(str)==1 )
System.out.print( node.data + " ");
if (m.containsKey(str))
m.put(str, m.get(str) + 1);
else
m.put(str, 1);
return str;
}
// Wrapper over inorder()
static void printAllDups(Node root)
{
m = new HashMap<>();
inorder(root);
}
// Driver code
public static void main(String args[])
{
Node root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(2);
root.right.left.left = new Node(4);
root.right.right = new Node(4);
printAllDups(root);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to find averages of
# all levels in a binary tree.
# Helper function that allocates a
# new node with the given data and
# None left and right pointers.
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def inorder(node, m):
if (not node):
return ""
Str = "("
Str += inorder(node.left, m)
Str += str(node.data)
Str += inorder(node.right, m)
Str += ")"
# Subtree already present (Note that
# we use unordered_map instead of
# unordered_set because we want to print
# multiple duplicates only once, consider
# example of 4 in above subtree, it
# should be printed only once.
if (Str in m and m[Str] == 1):
print(node.data, end = " ")
if Str in m:
m[Str] += 1
else:
m[Str] = 1
return Str
# Wrapper over inorder()
def printAllDups(root):
m = {}
inorder(root, m)
# Driver code
if __name__ == '__main__':
root = None
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.right.left = newNode(2)
root.right.left.left = newNode(4)
root.right.right = newNode(4)
printAllDups(root)
# This code is contributed by PranchalK
C#
// A C# program to find all duplicate subtrees
// in a binary tree.
using System;
using System.Collections.Generic;
class GFG
{
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static Dictionary<String,
int> m = new Dictionary<String,
int>();
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
static String inorder(Node node)
{
if (node == null)
return "";
String str = "(";
str += inorder(node.left);
str += (node.data).ToString();
str += inorder(node.right);
str += ")";
// Subtree already present (Note that we use
// HashMap instead of HashSet
// because we want to print multiple duplicates
// only once, consider example of 4 in above
// subtree, it should be printed only once.
if (m.ContainsKey(str) && m[str] == 1 )
Console.Write(node.data + " ");
if (m.ContainsKey(str))
m[str] = m[str] + 1;
else
m.Add(str, 1);
return str;
}
// Wrapper over inorder()
static void printAllDups(Node root)
{
m = new Dictionary<String, int>();
inorder(root);
}
// Driver code
public static void Main(String []args)
{
Node root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(2);
root.right.left.left = new Node(4);
root.right.right = new Node(4);
printAllDups(root);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// A javascript program to find all duplicate subtrees
// in a binary tree.
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
/* A binary tree node has data, pointer to
left child and a pointer to right child */
let m;
function inorder(node)
{
if (node == null)
return "";
let str = "(";
str += inorder(node.left);
str += toString(node.data);
str += inorder(node.right);
str += ")";
// Subtree already present (Note that we use
// HashMap instead of HashSet
// because we want to print multiple duplicates
// only once, consider example of 4 in above
// subtree, it should be printed only once.
if (m.get(str) != null && m.get(str)==1 )
document.write( node.data + " ");
if (m.has(str))
m.set(str, m.get(str) + 1);
else
m.set(str, 1);
return str;
}
// Wrapper over inorder()
function printAllDups(root)
{
m = new Map();
inorder(root);
}
let root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(2);
root.right.left.left = new Node(4);
root.right.right = new Node(4);
printAllDups(root);
// This code is contributed by suresh07.
</script>
Producción
4 2
Complejidad de tiempo: O (N ^ 2) Dado que la copia de strings requiere O (n) tiempo adicional.
Espacio auxiliar: O(N^2) Dado que estamos procesando una string para cada Node y la longitud de esta string puede ser del orden N.
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.
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