프로그래밍 면접 문제 21: Tree Reverse Level Order Print
프로그래밍 면접 문제 21: Tree Reverse Level Order Print
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 20: Tree Level Order Print
이 문제는 이전에 포스팅한 level order print와 매우 유사합니다. 트리를 계층 순서대로 다시 출력하지만, 이번에는 아래부터 시작해서 루트(root) 계층으로 출력합니다. 전에 사용했던 것과 동일한 트리를 사용하면:
출력 값은 다음과 같습니다:
4 5 6
2 3
1
이 문제의 해결 방법은 level order print와 유사합니다. 트리의 루트(root)부터 넓이 우선 탐색(BFS)을 시작해 각 노드를 큐에 넣습니다. 아래에서 시작해서 위 방향으로 출력을 해야하고 넓이 우선 탬색(BFS)은 위에서 아래로 처리하기 때문에 이 시점에서는 노드를 출력하지 않습니다. 넓이 우선 탐색을 완료한 다음 별도의 루프(loop)에서 출력합니다. 또한 새 라인을 제 위치에 출력하기 위해서 각 계층의 노드 수를 기록해 스택(stack)에 저장합니다. 따라서 넓이 우선 탐색을 완료 후에 다음과 같은 두 가지 자료 구조를 갖게 됩니다.
노드 값이 저장된 큐: [1, 2, 3, 4, 5, 6]. 큐는 넓이 우선 탐색에 의해 위에서 아래로 그리고 왼쪽에서 오른쪽 방향으로 탐색이 완료된 후 생성되었습니다.
각 계층의 노드의 수가 저장된 스택: [3, 2, 1]. 이 자료구조는 스택이기 때문에 첫 번째 요소는 가장 깊은 계층의 노드 수를 나타내며, 마지막 요소는 항상 트리의 루트(root)에 해당하는 1을 나타냅니다.
이 두 개의 자료구조를 생성한 후 첫 번째 줄에 출력하려는 노드는 큐의 마지막 부분에 있습니다. 그리고 출력할 노드의 수는 스택 맨 위에 있습니다. 따라서 루프의 각 반복 작업에서 스택의 요소를 빼낸 다음 노드의 수를 확인하고 큐의 끝에서부터 이 수만큼 출력합니다. 위의 예제 트리를 사요하면, 첫 번째 줄의 출력에는 스택의 첫 번째 요소인 3개의 노드가 포함됩니다. 그리고 출력할 노드는 큐 끝의 3개의 노드 [4, 5, 6] 입니다. 두 번째 줄의 출력에는 스택의 두 번째 값인 2개의 노드가 포함됩니다. 이 노드들은 큐에서 첫 번째 줄 바로 전에 있는 2개의 노드로서 [2, 3] 입니다. 최종적으로, 마지막 줄의 노드는 스택의 마지막 요소인 1입니다. 그리고 출력할 노드는 큐의 시작 부분에 있으며 이는 1입니다.
코드는 다음과 같습니다:
def reverseLevelOrderPrint(tree):
if not tree:
return
nodes = [tree] #queue
levelCount = collections.deque([1]) #stack
currentCount, nextCount = 1, 0
i=0
while i < len(nodes):
currentNode = nodes[i]
currentCount -= 1
if currentNode.left:
nodes.append(currentNode.left)
nextCount += 1
if currentNode.right:
nodes.append(currentNode.right)
nextCount += 1
if currentCount == 0:
#finished this level
if nextCount == 0:
#no more nodes at next level
break
#continue with next level
levelCount.appendleft(nextCount)
currentCount, nextCount = nextCount, currentCount
i += 1
printIndex = len(nodes)
for count in levelCount:
output = nodes[printIndex-count:printIndex]
print ' '.join(map(str, output)), '\n',
printIndex -= count
이 문제는 가장 기본적인 자료 구조인 트리, 스택, 큐를 사용하는 훌륭한 문제입니다.
