Vérifier si un arbre binaire est une image miroir ou symétrique
Qu'est-ce que les bases de l'algorithme pour tester si un arbre est symétrique. Parce que c'est un arbre binaire, je suppose que ce serait une définition récursive de toutes sortes
Formelle question est ci-dessous:
Un arbre binaire est une image miroir de lui-même si son les sous-arbres gauche et droit sont identiques images en miroir c'est à dire, l'arbre binaire symétrique.
Cela est mieux expliqué par quelques exemples.
1
/\
2 2
VRAI
1
/\
2 2
\
3
FAUX
1
/ \
2 2
/\ /\
4 3 3 4
VRAI
1
/ \
2 2
/\ /\
3 4 3 4
FAUX
1
/ \
2 2
/ \
3 3
VRAI
Dans un langage de programmation de choix, de définir un Arbre class/struct C et une méthode associée à vérifier si l'arbre est une image de miroir. Pour les langages à typage statique, vous pouvez supposer que les valeurs de nœud sont tous les nombres entiers.
Class/structure definition
BTree {
BTree left;
BTree right;
int value;
}
Supposer que la racine de l'arbre est suivi par l'appelant et fonction isMirror() est appelée.
Aussi, si la définition d'une classe, assurez-vous de fournir un constructeur sans argument et les getter/setter si les éléments de données ne sont pas accessibles au public.
Vous devez vous connecter pour publier un commentaire.
Comment sur l'appel de mirrorEquals(de la racine.gauche, de la racine.droite) sur la fonction suivante :-
Fondamentalement comparer le sous-arbre gauche et de haut en bas à droite de la sous-arborescence, le dessin d'une ligne imaginaire de l'inversion à travers la racine.
if (left == null || right == null) return false;
true
.if (left == null && right == null) return true;
et la deuxième est que j'ai suggéré.Solution De 1 - De Manière Récursive:
Solution De 2 - De Manière Itérative:
Récursive et Itérative des solutions en Java en utilisant des approches discutées ci-dessus
Récursive
Itératif à l'aide de LinkedList comme un File d'attente
Cas De Test
Nœud de l'arborescence de classe
La solution récursive à partir de @gvijay est très clair, et voici une solution itérative.
Inspecter chaque ligne de l'arbre de haut en bas et de voir si les valeurs sont un palindrome. Si elles sont toutes alors, oui, c'est un miroir. Vous aurez besoin de mettre en œuvre un algorithme de visiter chaque ligne et inclure des valeurs null pour clairsemée d'arbres. En pseudo-code:
L'astuce est la conception de l'algorithme de parcourir les lignes d'un arbre avec une contrepartie qui éparses, les arbres doivent avoir des valeurs null en tant que détenteurs de place. Cette implémentation Java semble ok:
MODIFIER
Comme il a été souligné dans les commentaires, ma première version de l'algorithme a échoué pour certaines entrées. Je ne vais pas réinventer la roue, je vais vous donner un Python réponse à l'aide de @gvijay algorithme correct. Tout d'abord, une représentation de l'arbre binaire:
J'ai testé le code ci-dessus à l'aide de tous les arbres dans la question et les arbres qui ont été de retourner des résultats incorrects, comme mentionné dans les commentaires. Maintenant, les résultats sont corrects pour tous les cas:
BTree(BTree(None, None, 1), None, 1)
, ou de tout autre arbre dont les en-valeur de l'ordre de la liste est un palindrome. par exemple,BTree(BTree(BTree(None, None, 1), None, 2), None, 1)
.Ici est un C++ solution par gvijay
Ci-dessous la solution est-à-vis de C - COde
Si quelqu'un a besoin d'un Swift version, en voici une.
Une autre approche serait de simplement inverser l'un des sous-arbres, et de comparer les deux sous-arbres de façon simple.
Approche légèrement différente.
Comment faire un afinde de la traversée de l'arbre binaire de stocker toutes les données dans un structure de données comme un string/array.
Une fois la traversée terminée, vérifier si les éléments de votre tableau la forme d'un palindrome.
Pas aussi efficace de l'espace de sage (récursivité prend O(log(n)), cette méthode contes O(n)), mais cela fonctionnera aussi bien.
Solution itérative à l'aide approche légèrement différente en python. Utilisation queue1 pour stocker des enfants à gauche, dans l'ordre de gauche à droite et de queue2 pour stocker le droit des enfants dans l'ordre de droite à gauche et de les comparer pour l'égalité.
public class SymmetricTree {
}
à l'aide de python
J'ai pensé ajouter une solution en Python que certaines personnes pourraient trouver plus facile à comprendre que les autres approches. L'idée est la suivante:
+1
à la valeur retournée par la gauche de l'enfant.-1
à la valeur retournée par le droit de l'enfant.l+r
parentDonc si
l+r == 0
pour n'importe quel nœud de l'arbre, puis le sous-arbre ancré au niveau de ce nœud est symétrique. Par conséquent, la totalité de l'arbre est symétrique seulement sil+r == 0
à la racine.Je ne suis pas très expérimenté (juste un an à l'entreprise), mais à mon avis, ce problème peut être résolu par l'utilisation de S=récursivité
Par exemple:
Retourne true si ça correspond.