4.9 BTS 수열

문제 

배열의 원소를 왼쪽에서부터 차례로 트리에 삽입함으로써 이진탐색트리를 생성할 수 있다. 이진 탐색 트리안에서 원소가 중복되지 않는다고 할때 해당 트리를 만들어 낼 수 있는 가능한 배열을 모두 출력하여라

 

예제 

입력 : 

출력 : { 2, 1, 3 } {2, 3, 1}

 

접근법

배열의 원소를 왼쪽부터 차례로 트리에 삽입함으로써 주어진 이진 탐색 트리를 만들기 위해서는

1. 리스트의 첫번째 노드는 무조건 root 노드여야 한다!

2. 왼쪽 부분트리의 노드가 먼저나오든, 오른쪽 부분 트리의 노드가 먼저 나오는 것은 중요하지 않다. ( 어쩌피 2 다음에는 순서에 상관없이 3은 오른쪽으로 1은 왼쪽으로 생성될 것이기 때문에 ) 

3. 그렇기 때문에 현재 노드의 왼쪽 부분트리와 오른쪽 부분트리에서 만들어질 수 있는 가능한 배열을 엮어서서 현재 노드까지를 하나의 트리로 볼 때의 가능한 배열을 모두 구할 수 있다. 엮을 때에 각 배열들의 상대 순서는 지켜져야 한다! 

array 1 : {1,2}

array 2 : {3,4}

weaved : {1,2,3,4}. {1,3,2,4} {1,3,4,2} ,{3,1,2,4} {3,1,4,2} {3,4,1,2}

 이런 식으로 말이다!

그리고 각 리스트의 가장 앞에에는 현재노드 (root)의 data가 들어가면 현재 노드까지를 트리로 봤을때 가능한 모든 배열을 구할 수있다.

각 노드까지의 가능한 배열을 말단 노드부터 재귀적으로 구하면 되고, 두개의 리스트를 엮는 과정도 재귀적으로 해결할 수있다.

def allSeq(root):
    result = []
    if root is None :
        return result.append([])
    
    seq_l = allSeq(root.left)
    seq_r = allSeq(root.right)
    prefix = [root.data]

    for sl in seq_1:
        for s2 in seq_2:
            weaved = []
            weaveList(s1, s2, weaved , prefix)
            result += weaved
    return result

def weaveList(l1, l2, results ,prefix):
    if len(l1) ==0 or len(l2) ==0:
        result = prefix + l1 + l2
        results.append(result)
        return

    prefix.append(l1.pop())
    weaveList(l1,l2,results,prefix)
    l1.append(prefix.pop())

    prefix.append(l2.pop())
    weaveList(l1,l2,results,prefix)
    l2.append(prefix.pop())
    return