Trouver le chemin lexicographiquement le plus petit du palindrome dans un arbre binaire

L'arbre binaire est une structure de données de base en informatique, offrant un moyen efficace d'organiser les données de manière hiérarchique. En parcourant ces arbres, nous rencontrons souvent des problèmes de calcul intéressants. Parmi eux, déterminer le chemin palindromique lexicographiquement le plus petit constitue un défi fascinant. Cet article illustre un algorithme C++ efficace pour résoudre ce problème et fournit des exemples détaillés pour une meilleure compréhension.

Énoncé du problème

Dans un arbre binaire où chaque nœud représente une lettre anglaise minuscule, notre objectif est de trouver le chemin palindrome lexicographiquement le plus petit. Si plusieurs chemins correspondent aux critères, nous pouvons renvoyer n'importe lequel d'entre eux. Si aucun chemin palindrome n’existe, nous devons renvoyer une chaîne vide.

Méthode

Notre solution à ce problème consiste à parcourir un arbre binaire à l'aide d'une technique de recherche en profondeur (DFS). La méthode DFS nous permet d'explorer tous les chemins depuis le nœud racine jusqu'aux nœuds feuilles.

Solution C++

C'est le code C++ qui implémente la méthode ci-dessus -

Exemple

#include<bits/stdc++.h>
using namespace std;

struct Node {
   char data;
   Node *left, *right;
   Node(char c) : data(c), left(NULL), right(NULL) {}
};

string smallestPalindrome(Node* node, string s) {
   if(node == NULL)
      return "";
   
   s += node->data;
   
   if(node->left == NULL && node->right == NULL)
      return string(s.rbegin(), s.rend()) == s ? s : "";
   
   string left = smallestPalindrome(node->left, s);
   string right = smallestPalindrome(node->right, s);
   
   if(left == "")
      return right;
   if(right == "")
      return left;
   
   return min(left, right);
}

string smallestPalindromicPath(Node* root) {
   return smallestPalindrome(root, "");
}

int main() {
   Node* root = new Node('a');
   root->left = new Node('b');
   root->right = new Node('a');
   root->left->left = new Node('a');
   root->left->right = new Node('a');
   root->right->left = new Node('b');
   root->right->right = new Node('a');
   
   cout << smallestPalindromicPath(root) << endl;
   
   return 0;
}

Sortie

aaa

Cas de test et instructions

Vérifions un arbre binaire avec la structure suivante -

     a
   /   \
  b     a
 / \   / \
a   a b   a

Dans cet arbre binaire, il existe plusieurs chemins depuis le nœud racine vers les nœuds feuilles. Parmi tous ces chemins, la fonction renvoie le chemin palindrome lexicographiquement le plus petit. Dans ce cas, les chemins palindromes possibles sont « aaa » et « aba ». Par conséquent, le résultat sera "aaa", qui est le plus petit chemin palindrome lexicographiquement.

Conclusion

La détermination du chemin palindrome lexicographiquement minimal dans un arbre binaire est un problème intéressant qui combine les concepts de traversée d'arbre et de manipulation de chaînes. La solution C++ fournie ci-dessus utilise une approche de recherche approfondie pour résoudre efficacement ce problème. Comprendre ces problèmes peut améliorer votre compréhension des arbres binaires et améliorer votre capacité à résoudre des problèmes informatiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!