문자열 배열의 유효한 이진 트리

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. 입력을 저장하고 각 노드를 삽입하는 동안 유효 또는 불량으로 표시하기 위해 트라이를 사용하십시오.

2. 입력 배열을 길이에 따라 정렬하십시오. 첫 번째 경우에는 {l, r, lr, rl, rlr}이됩니다
그리고 모든 입력을 넣을 문자열 세트를 만듭니다. 문자열의 길이가 1보다 길면 (rlr :: r, rl의 경우) 인덱스 0의 접두사를 모두 고려한 다음 set.if에서 접두어가 없으면 false를 반환합니다.
위의 방법에서보다 최적의 솔루션이나 수정이 있는지 궁금합니다.

Answer 1

다른 가능한 솔루션은 실제로 트리 (또는 트라이)를 작성하고 아직 불완전한 노드 집합을 유지 관리하는 것입니다.
목록 반복 처리를 완료했지만 여전히 불완전한 노드가 있으면 트리가 유효하지 않습니다.
집합이 비어 있으면 트리가 유효합니다.

예를 들어 두 번째 트리에서 노드 ll에 대해 노드 l을 만들지 만 불완전한 집합에 추가합니다. 이후 노드 중 하나가 l이면 세트에서 지울 것입니다. 그렇지 않은 경우 이 누락 된 비어 있지 않은 세트로 반복을 종료합니다. 노드.