Invert Binary Tree

문제

주어진 이진 트리의 루트 노드(root)가 주어질 때, 이 트리의 좌우를 반전(Invert)시켜서 반환하는 프로그램을 작성하는 문제입니다. 즉, 트리에 있는 모든 노드의 왼쪽 자식과 오른쪽 자식의 위치를 서로 바꾸어야 합니다.

• 입력: 이진 트리의 루트 노드 root (노드의 개수는 0개에서 100개 사이)
• 출력: 좌우가 반전된 트리의 루트 노드

링크: https://leetcode.com/problems/invert-binary-tree

풀이: 재귀(Recursion)를 활용한 하향식 스왑(Swap)

트리의 특성을 활용하여, 부모 노드에서 자식 노드로 내려가며 재귀적으로 왼쪽과 오른쪽 서브트리를 교환하는 직관적인 풀이입니다. 이전의 '두 정렬 리스트 병합' 문제에서 재귀를 사용하셨던 것과 마찬가지로, 트리의 하위 구조(Sub-tree)에 동일한 작업을 반복 수행하는 문제에서 재귀가 매우 강력한 힘을 발휘합니다.

• 기저 조건 (Base Case): 탐색 중인 노드(root)가 null이라면, 더 이상 바꿀 자식이 없으므로 null을 반환하고 재귀를 종료합니다.
• 자식 노드 교환 및 재귀 호출 (Recursive Step):
  • 두 변수의 값을 교환하는 스왑(Swap)의 기본 원리인 임시 변수(tmp)를 활용합니다.
  • 현재 노드의 왼쪽 서브트리(root.left)를 임시 변수 tmp에 안전하게 저장해 둡니다.
  • 현재 노드의 왼쪽 자식(root.left) 자리에는, 오른쪽 서브트리를 통째로 반전시킨 결과(invertTree(root.right))를 재귀적으로 호출하여 연결합니다.
  • 현재 노드의 오른쪽 자식(root.right) 자리에는, 아까 임시로 저장해 두었던 왼쪽 서브트리를 반전시킨 결과(invertTree(tmp))를 호출하여 연결합니다.
• 결과 반환: 현재 노드(root)를 기준으로 좌우 서브트리의 반전 및 교체가 모두 끝났으므로, 완성된 현재 노드를 반환하여 상위 호출자에게 전달합니다.

코드

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 1. 기저 조건: 트리가 비어있거나 리프 노드를 넘어간 경우
        if (root == null) {
            return null;
        }

        // 2. 왼쪽 서브트리를 임시 저장
        TreeNode tmp = root.left;
        
        // 3. 오른쪽 서브트리를 반전시켜 왼쪽에 연결
        root.left = invertTree(root.right);
        
        // 4. 임시 저장해둔 왼쪽 서브트리를 반전시켜 오른쪽에 연결
        root.right = invertTree(tmp);

        // 5. 좌우가 뒤집힌 현재 루트 노드 반환
        return root;        
    }
}

알고리즘 분류

자료 구조 (Data Structures), 트리 (Tree), 재귀 (Recursion), 깊이 우선 탐색 (DFS)