processus derrière la pensée de déterminer si l'arbre binaire est symétrique

Question

Voici la description du problème:

Compte tenu d'un arbre binaire, vérifier si elle est un miroir de lui-même (c.-à-symétrique autour de son centre).

Par exemple, cet arbre binaire [1,2,2,3,4,4,3] est symétrique:

1 
/\ 
    2 2 
/\/\ 
3 4 4 3 

Mais les [1,2,2, null, 3, null , 3] n'est pas:

1 
/\ 
    2 2 
    \ \ 
    3 3 

provenant: Determine if tree is symmetric

J'ai pris beaucoup de temps pour résoudre le problème et la solution, je suis venu avec était de faire une traversée de commande de niveau et vérifier que les valeurs dans chaque niveau sont un palindrome. Cette implémentation a passé les tests sur leetcode. Cependant, quand j'ai lu l'éditorial, j'ai vu un programme récursif extrêmement court et j'ai eu du mal à comprendre.

public boolean isSymmetric(TreeNode root) { 
    return isMirror(root, root); } 

public boolean isMirror(TreeNode t1, TreeNode t2) { 
    if (t1 == null && t2 == null) return true; 
    if (t1 == null || t2 == null) return false; 
    return (t1.val == t2.val) 
     && isMirror(t1.right, t2.left) 
     && isMirror(t1.left, t2.right);} 

1. Comment peut-on prouver l'exactitude de la version récursive ci-dessus? (Je suppose que cela peut être prouvé inductivement?)
2. Quelqu'un peut-il esquisser le processus de pensée en trouvant une telle solution. Est-ce que vous vérifiez la solution en visualisant réellement la pile d'appels ou y a-t-il un bon cadre de réflexion de haut niveau pour raisonner sur de tels problèmes?

Je comprends que l'arbre est une structure de données récursive en elle-même dire composé de sous-arbre gauche et à droite qui suivent la même structure, mais pour une raison quelconque lorsque je tente de vérifier la validité de cette solution, je tente de visualiser les appels récursifs et finalement mes pensées s'emmêlent. This guy a fait un bon travail pour expliquer comment la pile d'appels se déroule alors que la récursivité se poursuit, mais je voulais juste améliorer mon processus de réflexion pour de tels problèmes récursifs "faciles" et donc poster ici.

(FWIW, je connais récursion/DFS/retours en arrière et comment le flux d'appels est mais je suis coincé à venir et de valider l'idée récurrente de haut niveau pour le problème ci-dessus)

Merci pour aider.

Answer 1

C'est l'une des solutions qui peuvent être faites avec un algorithme récursif. L'idée est de maintenir initialement deux références à la racine puis de déplacer une sous arborescence vers la gauche et l'autre vers la direction opposée et inverser la direction de la traversée pour que les deux enfants aient maintenant un nœud symétrique sur l'un ou l'autre des sous-arbres (s'il existe)

Ici t1 et t2 fait référence aux sous-arbres gauche et droit.

if (t1 == null || t2 == null) return false; 

Qu'est-ce que cette étape fait est de vérifier s'il existe à la fois un sous-arbre à droite et à gauche parce que dans le cas où nous n'avons soit un sous-arbre alors il ne peut pas être symétrique qui nous ramène false

if (t1 == null && t2 == null) return true; 

Cela prend en compte les nœuds feuille où il est possible d'avoir null comme arbre enfant gauche et droit.Donc nous revenons vrai;

return (t1.val == t2.val) 
     && isMirror(t1.right, t2.left) 
     && isMirror(t1.left, t2.right);} 

peut être re écrit

if(t1.val != t2.val) return false; 
auto left = isMirror(t1.right, t2.left) 
auto right = isMirror(t1.left, t2.right); 
return left && right 

Maintenant que nous savons que les deux sous-arbre sont valides (i.e. non nul), nous vérifions alors pour leur valeur pour vérifier si elles sont les mêmes. Si ce n'est pas le cas, nous pouvons retourner faux car il ne sert à rien de chercher plus loin. La raison pour laquelle nous pouvons comparer est parce que puisque nous savons qu'il doit être un arbre binaire complet pour être symétrique, nous pouvons déplacer le sous-arbre gauche (t1) vers le sous-arbre gauche et droit (t2) vers la droite pour déplacez le noeud symétrique sur l'arbre secondaire droit.

     1 (t1, t2) 
        /\ 
        2 2 
        /\/\ 
        4 5 5 4 

Après isMirror(t1.right, t2.left)

     1 
        /\ 
       (t2) 2 2(t1) 
        /\/\ 
        4 5 5 4 

Après avoir appelé isMirror(t1.right, t2.left) récursive à nouveau

     1 
        /\ 
        2 2 
        /\/\ 
       (t2) 4 5 5 4(t1) 

Maintenant, ce sera à son tour appeler son enfant nœuds pour revenir vrai car ils sont tous deux nuls. Ensuite, la valeur de t1 et t2 est vérifiée et renvoie true ou false. Et puis isMirror(t1.left, t2.right) est appelé maintenant pour atteindre ici.

     1 
        / \ 
        2  2 
       /\ /\ 
        4 5 5 4 
        (t2)(t1) 

Qui fait maintenant la même chose que l'étape précédente et déroule la pile d'appels.

Ainsi, au cadre de pile nous avons left indiquant si le sous-arbre gauche du t1 est symétrique par rapport à l'arbre droit de sous t2 et right indiquant le contraire.

Puisque nous avons déjà vérifié si t1.val égale t2.val avant de vérifier récursive pour ses enfants, nous savons que la racine est égale et si elle est les enfants sont égaux qui nous ramène return left && right l'arbre secondaire de t1 est symétrique à l'arbre secondaire de t2

Si cela devient un peu compliqué, vous pouvez le tracer sur un papare et vérifier que cela pourrait éclaircir les choses beaucoup mieux.

Espérons que cela aide.

Answer 2

Comment peut-on prouver l'exactitude de la version récursive ci-dessus? (I suppose que cela peut être prouvé inductivement?)

Oui, vous pouvez le prouver par induction. Quelqu'un peut-il esquisser le processus de pensée en proposant une telle solution . Est-ce que vous vérifiez la solution en visualisant réellement l'appel pile ou est-ce qu'il y a un bon cadre de pensée de haut niveau pour raisonner sur de tels problèmes? J'ai résolu le problème dans les deux sens - traversée d'ordre de niveau et récursivité. En voyant ce problème, ma première pensée a été d'utiliser la traversée d'ordre de niveau.Et il n'y a pas de honte à penser solution sous-optimale (avec un espace supplémentaire) à la première tentative. Ensuite, j'ai compris l'approche récursive.

Je pense que tout cela concerne la pratique. Plus vous résolvez de problème de récursivité, plus vous commencez à penser/visualiser dans la tête l'arbre de récursion correspondant. Au début, je me suis battu avec lui et utiliser l'aide du débogueur pour voir le contenu de la pile de fonction dans chaque appel. Mais le débogage prend du temps et vous ne pouvez pas trouver de portée à déboguer dans le codage du tableau blanc. Maintenant à mon niveau, je peux comprendre le problème de récursion facile/moyen en le voyant en tête et dur en simulant dans un stylo & papier/tableau blanc.

Ces choses vont s'améliorer avec l'expérience et plus de pratique. Expérience avec certaines questions de structure de données - La personne qui voit et résout beaucoup de problème d'arbre binaire (représentation de pointeur)/BST sera plus susceptible de surpasser ici que la personne qui peut traiter la récursion très bonne mais n'a pas résolu le problème d'arbre binaire beaucoup.

Espérons que cela aide!