Invert/Flip Binary Tree

문제 링크

• https://leetcode.com/problems/invert-binary-tree/

문제 설명

이진 트리의 루트가 주어질 때, 이 트리를 뒤집고 그 루트를 반환하는 함수를 작성하세요. 이진 트리를 뒤집는다는 것은 각 노드의 왼쪽 자식과 오른쪽 자식을 교환하는 것을 의미합니다.

예제

• 예제 1
  • 입력: root = [4,2,7,1,3,6,9]
  • 출력: [4,7,2,9,6,3,1]
  • 설명: 주어진 트리는 다음과 같은 구조입니다.

            4
           / \
          2   7
         / \ / \
        1  3 6  9

    이 트리를 뒤집으면 다음과 같습니다.

            4
           / \
          7   2
         / \ / \
        9  6 3  1

• 예제 2
  • 입력: root = [2,1,3]
  • 출력: [2,3,1]
  • 설명: 주어진 트리는 다음과 같습니다.

        2
       / \
      1   3

    뒤집으면:

        2
       / \
      3   1

• 예제 3
  • 입력: root = []
  • 출력: []
  • 설명: 빈 트리는 뒤집혀도 여전히 빈 트리입니다.

풀이 전략

이 문제를 해결하기 위해 사용할 수 있는 방법은 다음과 같습니다.

1. 재귀적 접근:
   • 각 노드에 대해 왼쪽과 오른쪽 자식을 교환하고, 각각의 서브트리에 대해 재귀적으로 같은 작업을 수행합니다.
2. Iterative 접근 (DFS):
   • 스택을 사용하여 노드를 뒤집는 방법도 있습니다.
3. Iterative 접근 (BFS):
   • 큐를 사용하여 너비 우선 탐색(BFS) 방식으로 노드를 뒤집는 방법도 고려할 수 있습니다.

여기서는 재귀적 접근을 중심으로 설명합니다.

코드 분석

재귀적 접근

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None  # 빈 트리인 경우

        # 현재 노드의 왼쪽과 오른쪽 자식을 교환
        root.left, root.right = root.right, root.left

        # 왼쪽과 오른쪽 서브트리를 재귀적으로 뒤집음
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root  # 뒤집힌 트리의 루트 반환

• 동작 원리:
  • 첫 번째 조건으로 노드가 None인 경우, 빈 트리를 반환합니다.
  • 두 번째로 현재 노드의 왼쪽 자식과 오른쪽 자식을 교환합니다.
  • 그런 다음 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀적으로 invertTree 함수를 호출합니다.
  • 마지막으로, 뒤집힌 트리의 루트를 반환합니다.
• 시간 복잡도: (O(n)) - 모든 노드를 한 번씩 방문하여 교환 작업을 수행합니다.
• 공간 복잡도: (O(h)) - 재귀 호출 스택의 깊이는 트리의 높이에 비례하며, 최악의 경우 (h)는 (n)과 같을 수 있습니다 (편향 트리).

요약

• 이진 트리를 뒤집는 문제로, 재귀적 접근을 통해 각 노드의 왼쪽과 오른쪽 자식을 교환하는 방식으로 해결할 수 있습니다.
• 시간 복잡도는 (O(n))이며, 공간 복잡도는 트리의 높이에 따라 (O(h))입니다.