문제
A Binary Search Tree (BST) is a binary tree where every node has a value and the tree is arranged so that, for any node all the values in its left subtree are less than the node’s value, and all the values in its right subtree are greater than the node’s value.
To build a BST from a sequence of distinct integers the following procedure is used. The first integer becomes the root of the tree. Then the second integer in the sequence is considered. If it is less than the value of the root node then it becomes the left child. Otherwise, it becomes the right child. Subsequent items in the sequence move down either left or right in the same fashion depending on the comparison against earlier nodes, starting at the root and progressing down the tree. The new node is inserted (as a leaf) into the partially constructed tree when it reaches a missing subtree in the particular direction of travel.
For example, a BST generated by the sequence [2, 1, 4, 3] is built up as shown below as the numbers are inserted.
Figure 3: Generation of BST
The tree (d) of Figure 3 can also be generated by two other sequences: [2, 4, 3, 1] and [2, 4, 1, 3].
Such sequences can be compared according to a lexicographic order, where the comparison proceeds left-to-right and items at corresponding positions are compared using their numerical values. The result for [2, 1, 4, 3], [2, 4, 3, 1] and [2, 4, 1, 3] is as follows, using “<” to denote this lexicographic order between sequences: [2, 1, 4, 3] < [2, 4, 1, 3] < [2, 4, 1, 3].
For the tree (d) in Figure 3 the lexicographically least sequence is [2, 1, 4, 3].
Write a program that will read a representation of a tree and will generate the lexicographically least sequence of distinct positive integers that will generate that tree. Note that for a tree with n nodes this sequence will be a permutation of the numbers from 1 to n.
For the input to our problem we represent (recursively) the structure of a tree as follows:
A single node (a leaf) is a tree:
()
- If TL and TR are trees then the following are also trees:
(TL,)
(,TR)
(TL,TR)
입력
Input will consist of a sequence of lines. Each line will consist of up to 250 characters and will contain the specification of a single tree according to the above definition (with no intervening spaces). The sequence will be terminated by a tree consisting of a single node (). This line should not be processed.
출력
Output will be a sequence of lines, one for each line in the input. Each line will consist of the required permutation of the integers from 1 to n (where n is the number of nodes in the tree) separated by single spaces.
소스코드
def inorder(v) : #중위 순회
if leftChild.get(v) != None :
inorder(leftChild[v])
numbers.append(v)
if rightChild.get(v) != None :
inorder(rightChild[v])
while 1 :
tree = input()
if tree == '()' : #입력값이 ()라면 종료
break
stack = []
leftChild = dict() #{부모 노드 : 왼쪽 자식 노드}
rightChild = dict() #{부모 노드 : 오른쪽 자식 노드}
num = 0 #노드 번호
#트리 구성
for i in range (len(tree)) :
left = 0
right = 0
if tree[i:i+1] == '(' :
stack.append(num)
num += 1
elif tree[i:i+1] == ')' :
node = stack.pop()
if tree[i+1:i+2] == ',' :
leftChild[stack[-1]] = node
elif tree[i+1:i+2] == ')' :
rightChild[stack[-1]] = node
#번호 부여
numbers = [] #중위순회를 돌았을 때 지나가는 노드의 번호 순서
binary = dict() #{dfs 순서대로 부여된 번호 : binary tree 형식으로 부여된 번호}
i = 1
inorder(0)
for i in range (len(numbers)) : #중위순회로 지나간 노드 순서대로 1부터 번호 부여
binary[numbers[i]] = i + 1
for i in range (len(numbers)) : #dfs 순서대로 번호 출력
print(binary[i], end=' ')
print()문제가 영어긴 한데, 해석만 잘 하면 별로 어렵지 않습니당
간단하게 설명하면 입력이
((),((),))
이런 식으로 들어오는데
제일 바깥에 있는 괄호가 root node이고,
컴마 왼쪽에 괄호가 있으면 left child node, 오른쪽에 괄호가 있으면 right child node입니다
괄호 안에 있는 괄호는 바깥 괄호의 child node라고 보면 됩니다
그리고 입력으로 ()가 들어오면 이 줄은 처리하지 않고 종료합니다
이렇게 들어온 입력을 이용해 트리를 구성하고, 이 트리에 binary tree 형식으로 번호를 부여하고,
이 번호를 dfs 순서대로 출력하면 됩니다
저는 구성한 트리를 중위순회로 돌고, 그 순서대로 numbers 리스트에 노드 번호를 저장했습니다
그 순서를 다시 1번부터 번호를 부여하고, dfs 순서대로 출력합니다
조금 복잡하지만 디버깅해가면서 천천히 확인해보면 이해하기 쉽습니당..
사실 저도 푼지 오래돼서 기억이 안납니다...ㅋㅋㅋㅠ 죄송합니다
