[Leetcode] 104. Maximum Depth of Binary Tree_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '104. Maximum Depth of Binary Tree'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Maximum Depth of Binary Tree' 알고리즘 문제

 

STEP 2. 'Maximum Depth of Binary Tree' 코드(code)

 

STEP 3. 'Maximum Depth of Binary Tree' 해설

 

STEP 4. 'Maximum Depth of Binary Tree' solution

 

반응형

 

STEP 1. 'Maximum Depth of Binary Tree' 알고리즘 문제

 

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

이진트리의 루트 노드 'root'가 주어졌을 때, 트리의 최대 깊이를 반환하세요.

이진트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지의 경로에 있는 노드의 수를 의미합니다.

 

 

Constraints:

 

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

---

STEP 2. 'Maximum Depth of Binary Tree' 코드(code)

 

■ Runtime: 0ms Beats 100.00%
■ Memory: 19.12MB Beats 30.01%

 

# 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 not root:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth= self.maxDepth(root.right)

        depth = 1 + max(left_depth, right_depth)

        return depth

---

STEP 3. 'Maximum Depth of Binary Tree' 해설

 

왼쪽 노드 및 오른쪽 노드의 깊이를 계산하기 위해, 각 노드를 재귀적으로 순환하도록 작성했습니다.

노드의 깊이는 각 방향에서 최대 깊이 max(left_depth, right_depth)에서 1개 노드를 더 해서 계산하며, 빈 노드인 경우 0을 리턴하는 조건을 적용했습니다.

 

 

STEP 4. 'Maximum Depth of Binary Tree' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 0ms Beats 100.00%
■ Memory: 19.03MB Beats 48.18%

 

# 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 not root:
            return 0

        q = deque()
        q.append(root)
        depth = 0

        while q:
            depth += 1

            for _ in range(len(q)):
                node = q.popleft()
                if node.left :
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

        return depth

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '104. Maximum Depth of Binary Tree'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.