Python으로 이진 트리 반전(Invert)하기: 재귀를 활용한 좌우 뒤집기 구현

이진 트리 반전이란?

이진 트리의 루트(root)가 주어졌을 때, 트리 전체를 좌우로 뒤집는 문제를 생각해 볼 수 있습니다. 즉, 루트의 왼쪽 서브트리와 오른쪽 서브트리를 서로 교환하고, 그 하위 자식 노드들 역시 재귀적으로 같은 방식으로 교환하는 것입니다.

예를 들어 아래와 같은 트리가 입력으로 주어지면,

반전 후에는 다음과 같은 형태가 됩니다.

문제 해결 접근 방법

이 문제는 재귀(Recursion)를 활용하면 매우 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 노드를 인자로 받는 solve() 메서드를 정의합니다.

• 현재 노드(root)가 None이라면 더 이상 진행할 필요가 없으므로 그대로 반환합니다. (재귀의 종료 조건)

• 오른쪽 자식에 대해 solve()를 호출한 결과를 왼쪽 자식에 대입하고, 왼쪽 자식에 대해 호출한 결과를 오른쪽 자식에 대입하여 두 서브트리를 교환합니다.

• 교환이 완료된 현재 노드(root)를 반환합니다.

핵심은 한 줄의 파이썬 튜플 할당(tuple assignment)으로 좌우를 동시에 교환할 수 있다는 점입니다. 임시 변수 없이 root.left, root.right = self.solve(root.right), self.solve(root.left)처럼 작성하면 깔끔하게 처리됩니다.

구현 예제

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

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=', ')
        inorder(root.right)

class Solution:
    def solve(self, root):
        if not root:
            return
        root.left, root.right = self.solve(root.right), self.solve(root.left)
        return root

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
inv = ob.solve(root)
inorder(inv)

입력

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

출력

15, 10, 7, 5, 4,

동작 원리 설명

위 코드에서 inorder() 함수는 중위 순회(in-order traversal)를 수행하여 트리의 값을 왼쪽 → 루트 → 오른쪽 순서로 출력합니다. 트리가 반전되면 중위 순회 결과가 기존과 정확히 반대 순서로 나타나므로, 반전이 올바르게 수행되었는지 확인하는 좋은 검증 도구가 됩니다.

실행 결과 15, 10, 7, 5, 4,는 원래 트리의 중위 순회 결과인 4, 5, 7, 10, 15,의 역순과 일치합니다. 이를 통해 좌우 반전이 성공적으로 이루어졌음을 알 수 있습니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.

• 공간 복잡도: O(h) — 재귀 호출 스택이 트리의 높이(h)만큼 사용됩니다. 최악의 경우(편향 트리) O(n)까지 증가할 수 있습니다.