[DSA][Trees] 01. Invert Binary Tree

LeetCode 226

 

01. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

 

 

[질문하기]

- 루트 노드가 None일 수 있나요? 그런 경우에는 None을 그대로 반환하나요?

 

[아이디어]

- 재귀를 이용해서 각 노드의 자식 노드를 순차적으로 탐색하고 왼쪽과 오른쪽 자식을 서로 바꿔준다.

 

 

[풀이 1] Depth First Search

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return None

        self.invertTree(root.left)
        self.invertTree(root.right)

        root.left, root.right = root.right, root.left

        return root

invertTree 함수의 호출과 swap의 순서에 따라  구현 방식에는 두 가지가 있을 수 있는데,

[1] 재귀 호출을 먼저 수행한 후 swap 하는 방식

왼쪽 자식 → 오른쪽 자식 → 현재 노드 순으로 처리되므로, post-order traversal과 유사하다.

 

[2] 현재 노드의 자식을 swap 한 후, 재귀 호출을 하는 방식

현재 노드 → 왼쪽 자식 → 오른쪽 자식 순으로 진행되기 때문에, pre-order traversal이라고 볼 수 있다.

 

 

⏱️ 시간복잡도

이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

재귀 호출로 인해 최대 O(h)의 콜 스택이 사용될 수 있기 때문에 (h는 트리의 높이)

평균적인 경우 (balanced tree) O(log n), 최악의 경우 (skewed tree) O(n)의 공간 복잡도를 가진다.