[파이썬 알고리즘 인터뷰][트리] 이진 트리의 최대 깊이

[파이썬 알고리즘 인터뷰][트리] 이진 트리의 최대 깊이

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

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

문제 정의

트리의 최대 깊이 출력

책에서 구현된 코드

def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 queue = collections.deque([root]) depth = 0 while queue: depth += 1 # 큐 연산 추출 노드의 자식 노드 삽입 for _ in range(len(queue)): cur_root = queue.popleft() if cur_root.left: queue.append(cur_root.left) if cur_root.right: queue.append(cur_root.right) # BFS 반복 횟수 == 깊이 return depth

기억해야할 기법

트리의 각 층에 대한 연산

각 층의 노드는 q에 삽입, for문이 len(q)만큼 돌면 각 층의 노드마다 탐색

최대, 최소에 대한 접근 BFS로 풀기

내가 구현한 코드

def maxDepth(root: TreeNode) -> int: def get_depth(node: TreeNode): if not node: return 0 return max(get_depth(node.left), get_depth(node.right)) + 1 return get_depth(root)

속도 결과도 비슷하고 코드 가독성도 책에 나온 내용보다 좋은 듯 하다

그러나 완전탐색해야하는 해당 문제에만 유효한 듯 보통 최대/최소 문제는 BFS를 통해 일찍 탐색을 종료할 수 있음 각 층에 대한 처리가 필요할 경우, DFS로는 어려울 수 있음 개인적으로 계층이 나누어진 트리를 계층 순으로 탐색하는 것이 더 직관적이라 생각함

from http://pythaac.tistory.com/112 by ccl(A) rewrite - 2021-08-03 14:26:39