Python으로 이진 트리 반전하기: 재귀 알고리즘 완벽 가이드

이진 트리(binary tree)가 주어졌을 때, 좌우를 뒤집은 반전된 이진 트리(inverted binary tree)를 만드는 것이 목표입니다. 예를 들어 아래와 같은 트리가 있다고 가정해 보겠습니다.

이 트리를 반전하면 모든 노드의 왼쪽 자식과 오른쪽 자식이 서로 교체되어, 거울에 비친 것처럼 좌우가 대칭으로 뒤집힌 형태의 트리가 됩니다.

문제 해결 접근 방식

이 문제는 재귀(recursion)를 이용하면 매우 간단하게 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.

• 루트(root)가 null이면 그대로 반환합니다. (빈 트리는 반전해도 빈 트리입니다)
• 현재 노드의 왼쪽 포인터와 오른쪽 포인터를 서로 교환(swap)합니다.
• 왼쪽 서브트리와 오른쪽 서브트리에 대해 같은 과정을 재귀적으로 수행합니다.

Python 구현 예제

아래 코드는 트리 생성, 레벨 순회 출력, 그리고 트리 반전 기능을 포함한 전체 구현 예제입니다.

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

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def height(root):
    if root is None:
        return 0
    else:
        # 왼쪽과 오른쪽 서브트리의 높이를 계산
        l_height = height(root.left)
        r_height = height(root.right)
        # 더 큰 값에 1을 더해 반환
        if l_height > r_height:
            return l_height + 1
        else:
            return r_height + 1

def print_given_level(root, level):
    if root is None:
        return
    if level == 1:
        print(root.data, end = ',')
    elif level > 1:
        print_given_level(root.left, level - 1)
        print_given_level(root.right, level - 1)

def level_order(root):
    h = height(root)
    for i in range(1, h + 1):
        print_given_level(root, i)

def insert(temp, data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.solve(root)
        return root

    def solve(self, root):
        if not root:
            return
        # 왼쪽과 오른쪽 자식 노드를 교환
        temp = root.left
        root.left = root.right
        root.right = temp
        # 각 서브트리를 재귀적으로 반전
        self.solve(root.left)
        self.solve(root.right)

tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
tree2 = ob1.invertTree(tree1)
level_order(tree2)

입력

[1,2,2,3,4,None,3]

출력

1,2,2,3,None,4,3,

시간 및 공간 복잡도

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 개수입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되며, 최악의 경우(편향된 트리) O(n), 균형 잡힌 트리의 경우 O(log n)입니다.