Day 66: Python 이진 트리 반전, 완벽한 트리 대칭을 위한 재귀적 미러 스와프 (LeetCode #226 스타일)

Source: Dev.to

Welcome to Day 66 of the #80DaysOfChallenges journey! This intermediate challenge focuses on inverting a binary tree by recursively swapping left and right children, transforming the structure into its mirror image while preserving values. It uses recursive traversal to flip subtrees, a fundamental technique for tree manipulations like symmetry checks or balancing. If you’re advancing from basic recursion to tree algorithms or prepping for interviews (LeetCode #226), this “Python invert binary tree” script demonstrates a function that’s elegant, in‑place, and easy to adapt for iterative versions.

💡 Key Takeaways from Day 66: Tree Inversion Function

1. Function Design: Recursive Swap and Base Case

def invert_tree(tree: dict, node):
    """Recursively invert the binary tree starting from the given node."""
    if node is None:
        return

    left, right = tree.get(node, (None, None))   # get left and right children
    tree[node] = (right, left)                   # swap children

    invert_tree(tree, left)   # invert left subtree
    invert_tree(tree, right)  # invert right subtree

• 기본 사례는 node가 None일 때 반환합니다.
• 자식 노드는 dict.get으로 가져오며 기본값은 (None, None)입니다.
• 튜플을 교환한 뒤 함수가 두 서브트리 모두에 재귀 호출됩니다.
• 복잡도: 시간 O(n), 공간 O(h) (여기서 h는 트리 높이).

2. Tree Structure: Dict‑Based Representation

tree = {
    "A": ("B", "C"),
    "B": ("D", "E"),
    "C": (None, "F"),
    "D": (None, None),
    "E": (None, None),
    "F": (None, None),
}

• 키는 노드 식별자이며, 값은 (left_child, right_child) 튜플입니다.
• 커스텀 노드 클래스를 사용하지 않는 작은 트리에 간단하고 편리합니다.

3. Main Demo: Before/After Inversion

root = "A"                    # root of the tree

print("Original tree:")
print(tree)

invert_tree(tree, root)       # invert the tree in‑place

print("\nInverted tree:")
print(tree)

• 출력은 루트의 자식이 교환된 것을 보여줍니다 (A는 ("C", "B")가 되며) 이 변환이 모든 서브트리에 재귀적으로 적용됩니다.

🎯 Summary and Reflections

• 재귀 패턴: 기본 사례 → 처리(교환) → 자식 재귀 호출.
• 트리용 딕셔너리: 클래스 기반 노드가 필요 없을 때 유연한 표현.
• 제자리(in‑place) 수정: 추가 메모리 할당을 피합니다.

가능한 확장으로는 스택이나 큐를 이용한 반복 버전, 혹은 원본과 반전된 구조를 비교해 트리 대칭성을 확인하는 용도가 있습니다.

🚀 Next Steps and Resources

• Source Code for Challenge #66: scripts/invert_binary_tree.py
• Main Repository: 80-days-of-challenges
• Daily Updates: Twitter/X (@Shahrouzlogs)