Comment puis-je retourner un bool dans une implémentation récursive de la profondeur de la première recherche?

Question

Je veux écrire une fonction pour vérifier si deux arbres binaires sont identiques.

Le code ressemble à:

bool checkSame(Node* first, Node* second) { 
    // Check if nodes are the same 

    // Check left nodes: checkSame(first->left, second->left) 
    // Check right nodes: checkSame(first->right, second->right) 

} 

Le problème est que je ne suis pas sûr de ce que pour revenir ici. Toutes les implémentations de DFS que j'ai trouvées ont une valeur de retour vide. Y a-t-il un où il retourne un bool?

Aussi, je cherche une solution récursive, pas une solution itérative.

Answer 1

Vous le faites exactement de la même manière que si vous appeliez d'autres fonctions au lieu de récurer.
(grand secret de récursivité est qu'il n'y a rien de spécial récursivité.)

Les arbres sont égaux si et seulement si

• les nœuds sont égaux, et
• ses deux sous-arbres sont égaux

si

return first->data == second->data 
    && checkSame(first->left, second->left) 
    && checkSame(first->right, second->right); 

Manipuler les valises vides laissées en exercice.