[LeetCode/Python] 104. 이진 트리의 최대 깊이(Maximum Depth of Binary Tree)

 

 

이진 트리의 최대 깊이를 구하라.

 

example:

 

Input: root = [3,9,20, null, null,15,7]

 

Output: 3

 

 

 

1. 내가 푼 코드

 

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        result = []
        def dfs(tree, i):
            if tree.left:
                dfs(tree.left, i + 1)
            if tree.right:
                dfs(tree.right, i + 1)
            if tree.left is None and tree.right is None:
                result.append(i)
                print(i)
                return
        if root is None:
            result.append(0)
        else:
            dfs(root, 1)
        return max(result)

 

해설:

 

트리의 깊이를 구하는 문제라서

 

dfs로 구현하였고 인자로 i(길이)를 넘겨주었다.

 

노드에서 더 이상 left나 right가 존재하지 않으면

 

result에 i를 추가하고 종료하도록 했고

 

root로 아무것도 주어지지 않을 것을 대비하여

 

line 19~20 코드를 추가하였다.

 

 

 

 

 

2. 반복 구조로 BFS 풀이

 

 

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

 

해설:

 

BFS로 구현하였다.

 

BFS의 경우 앵간해선 deque로 구현하는 것이 좋다.

 

왜냐하면 양방향 추출이 빈번할 경우 리스트보다 실행 속도가 빠르기 때문!

 

따라서 반복문 안에서 레벨 0, 레벨 1, 레벨 2... 순서대로 진행된다.

 

따라서 반복문이 끝날 때의 depth는 결국 트리의 깊이가 된다.