Действительное двоичное дерево из массива строки

Question

У меня есть массив строк. Каждый символ в строке может быть только r или l. я должен проверить, если это действительно или нет, как

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. 

От входа поддавки я должен определить, если он создает действительное дерево или нет. Я придумал два решения.

1. Использование trie для хранения ввода и маркировки каждого узла как действительного или нет при вставке.

2.Сортировать входной массив в соответствии с длиной. Итак, для первого случая это будет {l, r, lr, rl, rlr}
И я создам набор строк для ввода всех входных данных. Если строка имеет длину больше 1 (для rlr :: r, rl), я буду рассматривать все ее префикс из индекса 0 и проверять set.if любой префикс, отсутствующий в наборе, тогда я верну false.
Мне интересно, есть ли более оптимальное решение или любая модификация вышеуказанных методов.

Answer 1

Другое возможное решение - это, фактически, построение дерева (или trie) и поддержка набора узлов, которые еще не завершены.
Если вы закончите итерирование по списку и у вас все еще есть неполные узлы, дерево недействительно.
Если набор пуст, дерево является действительным.

Например, во втором дереве, которое вы указали, для узла ll вы также создадите узел l, но вы добавите его в неполный набор. Если один из более поздних узлов - l, вы удалите его из набора. Если нет, вы закончите итерацию непустым набором, который содержит вас отсутствует узлов.