[파이썬 알고리즘 인터뷰][트리] 이진 트리 반전

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

트리의 child들을 모두 반전

 

책에서 구현된 코드

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left, root.right = \
                self.invertTree(root.right), self.invertTree(root.left)
            return root
        return None

 

기억해야할 기법

• 단순 swap도 재귀로 구현
  
  • 재귀가 일어난 시점에서 어떤 연산이나 복잡한 과정이 필수적인 사항은 아님
  • 놀랍게 깔끔하다

 

내가 구현한 코드

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        q = deque([root])
        while q:
            node = q.popleft()
            if node:
                node.left, node.right = node.right, node.left
                q.append(node.left)
                q.append(node.right)
        return root

• 나는 책에 나온 "풀이2 반복 구조로 BFS"와 흡사하게 풀었다(거의 똑같다)
• 책에서 소개하는 4가지 풀이의 속도가 모두 비슷하다
• 그러나 재귀 or DFS로 처리하는게 공간효율이 더 좋은 것 같다
  • BFS로 풀면 루프마다 queue에 "레벨의 노드의 개수"만큼 저장
    - 전체 노드의 개수 : 2⁰ + 2¹ + 2² + ... + 2^k
    - 레벨 k의 노드의 개수 : 2^k-1
    - 즉, queue에 담기는 최대 노드의 수는 2^k-1
  • 재귀 or DFS로 풀면 stack에 "트리의 최대 깊이"만큼 저장
    - 즉, stack에 담기는 최대 노드의 수는 k-1
  • 트리의 최대 깊이가 10일 때
    - queue에는 최대 512개의노드가 담길 수 있음
    - stack에는 최대 10개의 노드가 담길 수 있음
• 모든 트리의 노드를 탐색해야하므로, 구현 방식에 따른 시간복잡도의 차이는 없음