Arbre binaire valide du tableau de la chaîne

Question

J'ai un tableau de chaînes.Chaque caractère dans une chaîne peut être r ou l seulement. Je dois vérifier si elle est valide ou non comme

1. {rlr,l,r,lr, rl} 

      * 
     / \ 
     l  r 
     \ /
      r l 
       \ 
       r 
A valid tree as all nodes are present. 




2. {ll, r, rl, rr} 
     * 
     /\ 
     - r 
    / /\ 
     l l r 

Invalid tree as there is no l node. 

A partir d'une entrée donneras, je dois déterminer si elle crée un arbre valide ou non. J'ai trouvé deux solutions. 1.Utiliser Trie pour stocker l'entrée et marquer chaque noeud comme valide ou non lors de l'insertion.

2.Sort le tableau d'entrée en fonction de la longueur. Donc pour le premier cas ce sera {l, r, lr, rl, rlr}
Et je vais créer un ensemble de chaînes pour mettre toutes les entrées. Si une chaîne a une longueur supérieure à 1 (pour rlr :: r, rl), je considérerai tout son préfixe à partir de l'index 0 et j'ajouterai set.if si le préfixe n'est pas présent dans l'ensemble, je retournerai false.
Je me demande s'il existe une solution plus optimale ou une modification dans les méthodes ci-dessus.

Answer 1

Une autre solution possible est en fait la construction de l'arbre (ou trie) et de maintenir un ensemble de nœuds qui sont encore incomplètes.
Si vous avez fini d'itérer sur la liste et que vous avez encore des nœuds incomplets, l'arborescence n'est pas valide.
Si l'ensemble est vide, l'arbre est valide. Par exemple, dans le deuxième arbre que vous avez donné, pour le noeud ll, vous allez également créer le noeud l, mais vous l'ajouterez à l'ensemble incomplet. Si l'un des derniers nœuds est l, vous l'effacerez de l'ensemble. Si ce n'est pas le cas, vous finirez l'itération avec un ensemble non vide qui contient manquant nœuds.