文字列の配列から有効なバイナリツリー

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. 

として有効であるかどうかをチェックする必要があります。 私は2つの解決策を考え出しました。

1.入力を保存し、挿入中に各ノードを有効または無効にマークするためにトライを使用する。

2.長さに従って入力配列をソートします。 最初のケースは{l、r、lr、rl、rlr}
となります。すべての入力を入れるための文字列を作成します。 文字列の長さが1より大きい場合（rlr :: r、rlの場合）、インデックス0のすべての接頭辞を考慮してset.ifをチェックし、接頭辞のいずれかが存在しない場合はfalseを返します。
私は、上記の方法でより最適な解決法または変更があるかどうか疑問に思っています。

Answer 1

実際にはツリー（またはトライ）を構築し、未完成のノードセットを維持することも考えられます。
リストを反復処理してもまだ不完全なノードがあると、ツリーは無効です。
セットが空の場合、ツリーは有効です。

たとえば、ノードllの場合は2番目のツリーにノードlも作成されますが、不完全なセットに追加されます。後のノードの1つがlの場合、セットから消去されます。そうでない場合は、が含まれていない空のセットで反復を終了します。ノード。