설명

LeetCode의 Invert Binary Tree 문제다.
위의 그림처럼 이진 트리가 주어졌을 때 이를 뒤집은 트리의 루트 노드를 반환하는 문제다.

풀이

루트 노드를 제외한 양쪽 서브 트리의 노드들을 모두 반전해야 하는데 처음에는 아래의 그림처럼 루트 노드부터 왼쪽 자식 노드를 오른쪽 자식 노드와 교환하면서 말단 노드까지 탐색해야겠다고 생각했다.
하지만 노드 1과 노드 9 같은 서로 멀리 떨어져 있는 말단 노드의 값을 어떻게 교환할 수 있을지 생각이 나지 않았다.
그래서 풀이를 찾아보니 마치 재귀 탐색처럼 루트 노드부터 말단 서브 트리까지 이동하면서 자신의 자식 노드만 반전시키는 방식이었다.

트리가 반전된다고 해도 루트 노드 입장에서는 양 쪽 자식 노드의 포인터만 바뀌면 되는 것이지 서브 트리의 내용까지는 신경 쓸 필요가 없기 때문이다. 그렇기 때문에 루트 노드에서 자신의 자식 노드만 반전시키고 서브 트리의 내용의 반전은 서브 트리의 루트 노드, 즉 자식 노드를 큐에 집어넣고 다음 탐색에 맡기는 방식으로 해결할 수 있었다.

이를 기반으로 구성한 코드는 다음과 같다.

import collections


class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # 루트 노드부터 자식 노드의 탐색을 위한 큐 역할의 덱 생성.
        queue = collections.deque([root])
        
        # 루트 노드부터 탐색.
        while queue:
            node = queue.popleft()
            if not node:
                continue
            
            # 자식 노드를 꺼내서 반전
            node.left, node.right = node.right, node.left
            # 서브 트리의 노드들도 반전시키기 위해 자식 노드를 큐에 삽입.
            queue.append(node.left)
            queue.append(node.right)

        return root

후기

처음에는 대체 무슨 말인가.. 했다가 탐색 코드를 보고 이해할 수 있었다. 트리 상태로만 보면 약간 재귀 느낌이 들기도 하지만 큐를 활용해서 현재 루트 노드의 양쪽 자식 노드 반전 후 서브 트리의 구성 노드들도 똑같은 기준으로 반전시키는 점이 인상깊었다.

처음에 생각했던 것처럼 양 끝단의 노드끼리 반전시키는 방법도 있을지 궁금하다.