[Leetcode 아주 상세한 문제풀이] 104. Maximum Depth of Binary Tree - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 104번 문제 Maximum Depth of BInary Tree 다.

우선 문제를 살펴보자.

 

리트코드 104번 문제 Maximum Depth of BInary Tree 링크

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

Maximum Depth of Binary Tree - LeetCode

 

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.

 

Example 1:

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

Example 2:
Input: root = [1,null,2]
Output: 2
 
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100

 

 

문제 설명

문제에 대해 간략히 살펴보자.

우선 binary tree에 대해 간략히 이해할 필요가 있다. Binary tree는 하나의 뿌리 (root)로 부터 두 개의 가지를 tree를 말한다. 문제 예시 1번에서보는 것처럼 하나의 뿌리 (3)에서 부터 두 개의 가지 (9와 20)가 갈라져 나온다. 그리고 갈라져 나온 가지 20에서 부터 15와 7이라는 두 개의 가지가 나온다. 하나의 뿌리로 부터 나오는 가지 개수는 1개나 3개가 될 수 없으며 (무조건 2개여야 하며), 가지가 없을 수는 있다.

문제에서 요구하는 바는 주어진 binary tree에 대하여 그 tree의 깊이 (depth)를 구하라는 뜻이다. 여기서 깊이란 문제 예시 1번에서 보는 것처럼 3이 첫번째 층, 9와 20이 두번째 층, 그리고 15와 7이 세번째 층으로 깊이가 3이다. 이처럼 도식으로 나타내면 깊이가 얼마인지 쉽게 파악할 수 있을 것이다.

이제 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위해서는 recursive approach를 이용할 것이다.

간단히 설명해 우리는 하나의 뿌리로 부터 시작해 왼쪽과 오른쪽 가지를 탐색한다.

이때 왼쪽, 오른쪽 가지 둘 다 혹은 둘 중 하나는 subtree를 가질 수 있다.

따라서 그 subtree를 또 다시 탐색해야 하고, 만약 그 subtree가 sub-subtree를 갖는다면 그것을 또 탐색해야 한다.

따라서 재귀함수를 이용하여 각 가지의 depth를 탐색해야 한다.

그 후 왼쪽 가지와 오른쪽 가지의 depth를 비교해 더 큰 값을 취한다. 

문제 예시 1번으로 돌아가보면 우선 뿌리 3에서 시작해 왼쪽 가지 9와 오른쪽 가지 20이 있다.

우리는 왼쪽과 오른쪽 가지의 depth를 탐색하는데 왼쪽 가지의 경우 subtree가 없으므로 depth는 1이고,

오른쪽 가지의 경우 subtree가 있으므로 그 subtree에 대한 depth 탐색을 재귀함수를 이용하여 진행한다.

그 결과 subtree의 왼쪽 가지 (15)와 오른쪽 가지 (7)은 depth가 같으므로,

오른쪽 가지 20의 subtree의 maximum depth는 1임을 알 수 있다.

다시 뿌리가 3인 왼쪽 가지 9와 오른쪽 가지 20인 케이스로 돌아와보면,

오른쪽 가지의 경우 subtree의 maximum depth가 1이고 자기 자신의 depth가 1이다.

따라서 뿌리 3을 기준으로 왼쪽 가지 9의 depth는 1 오른쪽 가지 20의 depth는 2임을 알 수 있다.

결과적으로 우리가 구하고자 하는 전체 binary tree의 maximum depth는 오른쪽 가지를 취해

오른쪽 가지의 depth 2와 뿌리 3 자신의 depth 1을 더해 총 3이된다

이제 코드로 한 번 살펴보자. 

 

 

문제 풀이

우선 binary tree을 위한 클래스를 선언해준다 (line 1)

self.val은 자신 (=뿌리)의 값을, self.left와 self.right은 그 뿌리의 왼쪽과 오른쪼 가지의 값을 의미한다 (line 4-6)

우리는 binary tree를 입력받을 함수를 정의해 준다 (line 8)

만약 그 binary tree에 아무것도 없다면 당연히 depth를 따질 필요가 없기 때문에 0을 리턴해준다 (line 10-11)

앞서 설명한대로 우리는 binary tree의 depth를 탐색하는 함수를 재귀호출 할 것이다.

여기서는 내장 함수 maxDepth를 이용하여 왼쪽과 오른쪽 가지의 maximum depth를 탐색한다 (line 13-14)

이 과정을 통해 각 가지가 가지고 있는 subtree의 maximum depth도 탐색된다.

Depth 탐색을 마치고 나면 뿌리로 부터 시작된 왼쪽 가지와 오른쪽 가지의 depth 값이 나오는데,

이를 서로 비교하여 큰 값을 취한 후 1을 더해 (뿌리 자신) 리턴해주면 된다 (line 16) 

 

 

문제 풀이 코드

# 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
 
def maxDepth(root: TreeNode) -> int:
    # Base case: if the node is None, return 0
    if not root:
        return 0
    # Recursively compute the depth of the left and right subtrees
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    # Return the maximum of the two depths plus one (for the current node)
    return max(left_depth, right_depth) + 1
 
# Example usage:
# Construct the tree for example 1
root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(maxDepth(root1))  # Output: 3
 
# Construct the tree for example 2
root2 = TreeNode(1, None, TreeNode(2))
print(maxDepth(root2))  # Output: 2

 

 

관련 문제

리트코드 98번 Validate binary search tree 문제 풀이 (링크)

리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)

리트코드 572번 Subtree of another tree 문제 풀이 (링크)

 

104. Maximum Depth of Binary Tree