코딩 테스트 대비! 파이썬으로 "이진 트리 반전" 문제 풀이

파이썬으로 "이진 트리 반전" 문제 풀이


문제 설명

이진 트리의 루트 노드가 주어졌을 때, 해당 트리를 반전(좌우 대칭)시키는 프로그램을 작성하세요.


예시

입력: root = [4,2,7,1,3,6,9]
출력: [4,7,2,9,6,3,1]


솔루션 코드

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

def invert_tree(root):
    if not root:
        return None

    # 좌우 자식 노드 반전
    root.left, root.right = root.right, root.left

    # 재귀로 반전 진행
    root.left = invert_tree(root.left)
    root.right = invert_tree(root.right)

    return root

코드 설명

1. 이진 트리 노드 클래스 TreeNode를 정의합니다.
2. invert_tree 함수에서 root가 None이면 None을 반환합니다.
3. root의 좌우 자식 노드를 서로 바꿉니다.
4. 재귀 호출을 통해 왼쪽 서브트리와 오른쪽 서브트리를 반전시킵니다.
5. 반전된 root 노드를 반환합니다.

이 풀이의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(h)입니다. 여기서 n은 노드의 개수, h는 트리의 높이입니다.

이 문제에서는 이진 트리 반전을 위해 재귀 방식을 사용합니다. 루트 노드에서 시작해 좌우 자식 노드를 바꾸고, 각 서브트리에 대해 동일한 작업을 재귀적으로 수행합니다. 이렇게 하면 전체 트리가 좌우 대칭이 됩니다.

이진 트리 문제를 풀 때는 대개 재귀 또는 반복(스택/큐 활용)으로 접근합니다. 이번 예제를 통해 재귀 호출 방식의 이진 트리 탐색을 연습해볼 수 있습니다. 트리 자료구조는 코딩 인터뷰에서 매우 자주 출제되므로 숙지할 필요가 있습니다.