字符串數組中的有效二叉樹

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中的任何前綴不存在於set中，然後我將返回false。
我想知道是否有更好的解決方案或上述方法的任何修改。

Answer 1

另一種可能的解決方案是實際構建樹（或trie）並維護一組尚未完成的節點。
如果您完成對列表的迭代並且仍然有不完整的節點，那麼該樹無效。
如果該集合是空的，那麼樹是有效的。

例如，在第二棵樹中，對於節點ll，您還將創建節點l，但您會將其添加到不完整的集合中。如果其中一個後面的節點是l，那麼您將從該組中刪除它。如果不是，您將以包含您的非空集合結束迭代，缺少節點。