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

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

---

출처 : 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로는 어려울 수 있음
  • 개인적으로 계층이 나누어진 트리를 계층 순으로 탐색하는 것이 더 직관적이라 생각함