프로그래밍 면접 문제 20: Tree Level Order Print
프로그래밍 면접 문제 20: Tree Level Order Print
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 19: Find Next Palindrome Number
정수를 값으로 갖는 이진 트리가 주어지면, 계층 순서대로 출력하는 문제입니다. 동일한 계층에 있는 숫자들 사이에는 공백을 포함하고, 다른 계층 사이에는 줄을 바꿔 출력합니다. 예를 들어 주어진 트리가 다음과 같을 때:
출력 값은 다음과 같습니다:
1
2 3
4 5 6
재귀는 깊이 우선 탐색과 유사한데 이 문제에서 필요한 것은 넓이 우선 탬색이기 때문에, 이 경우에는 재귀를 사용하는 것이 적절하지 않습니다. 따라서 이전에 넓이 우선 탐색에서 했던 것처럼 큐(queue)를 사용하겠습니다. 먼저 큐에 루트 노드를 삽입합니다. 그런 다음 while 루프를 시작해 큐가 비어있을 때까지 루프를 실행합니다. 각 반복 과정에서는 큐의 시작 부분에서 노드를 빼내고(pop) 이 노드의 자식 노드를 큐의 끝에 삽입합니다. 노드를 빼내면 이 노드의 값과 공백을 출력합니다.
제 위치에 새 라인(줄바꿈)을 출력하기 위해서는 각 계층(레벨)의 노드 수를 계산해야 합니다. 이를 위해 현재 레벨 카운트와 다음 레벨 카운트 2개의 카운트(count)를 사용합니다. 현재 레벨 카운트는 새 라인을 출력하기 전에 현재 레벨에서 인쇄해야하는 노드 수를 나타냅니다. 큐에서 요소를 빼내고 출력할 때마다 이 카운트를 하나씩 감소시킵니다. 현재 레벨 카운트가 0에 도달하면, 새 라인을 출력합니다. 다음 레벨 카운트는 다음 레벨의 노드 수를 포함하며, 새 라인을 출력한 다음에는 현재 레벨 카운트가 됩니다. 현재 레벨에서 노드의 자식 수를 계산해서 다음 노드 수를 계산합니다. 다음 코드를 이해하는 것이 설명을 이해하는 것보다 더 쉽습니다.
class Node:
def __init__(self, val=None):
self.left, self.right, self.val = None, None, val
def levelOrderPrint(tree):
if not tree:
return
nodes = collections.deque([tree])
currentCount, nextCount = 1, 0
while len(nodes) != 0:
currentNode = nodes.popleft()
currentCount -= 1
print currentNode.val,
if currentNode.left:
nodes.append(currentNode.left)
nextCount += 1
if currentNode.right:
nodes.append(currentNode.right)
nextCount += 1
if currentCount == 0:
#finished printing current level
print '\n',
currentCount, nextCount = nextCount, currentCount
이 해결 방법의 시간 복잡도는 O(N)으로, 여기에서 N은 트리 내의 노드의 수를 나타냅니다. 각 노드를 적어도 한 번은 확인해야 하기 때문에 최적의 방법입니다. 시간 복잡도는 특정 시점에서 큐의 크기에 따라 다르며, 한 계층(레벨)에서 가장 많은 수의 노드에 따라 결정됩니다. 최악의 경우는 트리가 완전한 이진 코드일 때 발생하며, 이는 각 계층이 가능한 최대의 노드 수로 완전히 채워졌다는 것을 의미합니다. 이 경우, 가장 많은 수의 노드는 가장 마지막 계층에서 나타나며, N이 전체 노드일 때 (N + 1) / 2가 됩니다. 따라서 공간 복잡도 또한 O(N)입니다. 큐를 사용했음에도 최적입니다.
이 문제는 트리에 관한 가장 일반적인 면접 문제 중 하나이기 때문에 기본적으로 알아두시는 것이 좋습니다.
