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

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

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

출처 : 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 0 + 2 1 + 2 2 + ... + 2 k

- 레벨 k의 노드의 개수 : 2 k-1

- 즉, queue에 담기는 최대 노드의 수는 2 k-1 재귀 or DFS로 풀면 stack에 "트리의 최대 깊이"만큼 저장

- 즉, stack에 담기는 최대 노드의 수는 k-1 트리의 최대 깊이가 10일 때

- queue에는 최대 512개의노드가 담길 수 있음

- stack에는 최대 10개의 노드가 담길 수 있음

모든 트리의 노드를 탐색해야하므로, 구현 방식에 따른 시간복잡도의 차이는 없음

from http://pythaac.tistory.com/115 by ccl(A) rewrite - 2021-08-03 17:01:14