코딩 테스트 대비! 트리 순회(Traversal) 알고리즘 구현하기

트리 순회(Traversal) 알고리즘 구현하기


문제 설명

이진 트리가 주어졌을 때, 전위(preorder), 중위(inorder), 후위(postorder) 순회 방식으로 트리를 탐색하는 알고리즘을 구현하라.

예시 입출력

입력 트리:
     1
    / \
   2   3
  / \
 4   5

전위 순회 출력: 1 2 4 5 3
중위 순회 출력: 4 2 5 1 3  
후위 순회 출력: 4 5 2 3 1

솔루션 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    result = []
    
    def traverse(node):
        if node:
            result.append(node.val)
            traverse(node.left)
            traverse(node.right)
            
    traverse(root)
    return result

def inorder(root):
    result = []
    
    def traverse(node):
        if node:
            traverse(node.left)
            result.append(node.val)
            traverse(node.right)
            
    traverse(root)
    return result

def postorder(root):
    result = []
    
    def traverse(node):
        if node:
            traverse(node.left)
            traverse(node.right)
            result.append(node.val)
            
    traverse(root)
    return result

# 테스트 케이스
node1 = TreeNode(1)  
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5

print("전위 순회:", preorder(node1))
print("중위 순회:", inorder(node1))  
print("후위 순회:", postorder(node1))

코드 설명

이 문제에서는 재귀를 활용한 트리 순회 알고리즘 구현 방법을 다룹니다. 전위, 중위, 후위 순회는 트리 문제를 풀 때 기본적으로 요구되는 기술이므로 반드시 학습해야 합니다.

코드에서는 각 순회 방식에 맞게 재귀 함수 내부에서 현재 노드의 값을 결과 리스트에 추가하는 시점을 달리했습니다.

- 전위 순회: 현재 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
- 중위 순회: 왼쪽 자식 -> 현재 노드 방문 -> 오른쪽 자식  
- 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 현재 노드 방문

이렇게 순회 순서만 달리하면 전위, 중위, 후위 순회 알고리즘을 모두 구현할 수 있습니다.

트리 문제를 효과적으로 풀기 위해서는 재귀적 사고력과 다양한 순회 기법에 대한 이해가 필수적입니다. 트리의 속성을 잘 파악하고, 적절한 순회 방식을 선택하는 능력이 요구됩니다. 이번 포스팅을 통해 그러한 기본 역량을 기를 수 있습니다.