Après beaucoup de travail et un peu d'aide, je suis venu avec une solution O (n log n) qui se trouve également être correct à 100% du temps. Il est basé sur 2 idées:
Idée 1: Un arbre peut être représenté comme une chaîne qui répertorie ses sous-arbres. Par exemple, une feuille peut être représentée par "L". Un arbre qui a 2 feuilles peut être représenté par "(L), (L)". Un arbre qui a un sous-arbre qui a 2 feuilles peut être représenté par "((L), (L))", etc. Le problème avec cette approche est que les grands arbres conduiront à de longues chaînes répétitives, ce qui ralentira la algorithme bas.
Idée 2: Les chaînes peuvent être indexées dans un hashmap. Plutôt que de transporter une sous-chaîne comme "((L), (L))", nous pouvons attribuer à cette chaîne un numéro d'index, disons 2. Maintenant, nous pouvons faire référence à ce sous-arbre et à tous les sous-arbres Représentation de chaîne. Les chaînes sont les clés de la hashmap et les valeurs sont des entiers uniques affectés à ces chaînes.
Voici le code pour la construction du hashmap du premier arbre:
Notre premier appel devrait être fill(root, -1, 1)
public static int fill(int current, int previous, int height) {
ArrayList<Integer> subtrees = new ArrayList<>();
for (int next : edges[current]) {
if (next == previous) continue;
int subtree = fill(next, current, height+1);
subtrees.add(subtree);
}
// We have to sort subtrees for "2,4" and "4,2" to be considered the same
Collections.sort(subtrees);
StringBuilder sb = new StringBuilder(height + ".");
for (Integer subtree : subtrees) {
sb.append(subtree +",");
}
String key = new String(sb);
if (map.containsKey(key)) return map.get(key);
int index = map.size(); // assigning next available number
map.put(key, index);
return index;
}
Nous pouvons maintenant appeler remplir Tree 2 (remplacer "arêtes" avec arbre 2 informations, gardez le HashMap tel quel). Si elle renvoie le même nombre entier, les arbres correspondent.
Beaucoup de crédit à http://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf
Si vous avez deux enfants, alors évidemment le résultat est 31a + b. Cela ne gère pas l'isomorphisme. –
À moins que je ne me trompe, vous n'incorporez pas la valeur de nœud réelle dans votre hachage, ce qui semble assez important ...? –
Nous voulons savoir si la forme des arbres est la même, nous pouvons ignorer les valeurs des nœuds. –