프로그래밍 면접 문제 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) 계층으로 출력합니다. 전에  사용했던 것과 동일한 트리를 사용하면:

binaryTree

출력 값은 다음과 같습니다:
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

이 문제는 가장 기본적인 자료 구조인 트리, 스택, 큐를 사용하는 훌륭한 문제입니다.

 

다음글 – 프로그래밍 면접 문제 22: Find Odd Occurring Element

RonnieJ

프리랜서 IT강사로 활동하고 있습니다. 게임 개발, 웹 개발, 1인 기업, 독서, 책쓰기에 관심이 많습니다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다