공부블로그

오늘의 공부 키워드

• 이진검색 트리(BST) 트리 최대 깊이 관련 내용 
• 104 Maximum Depth of Binary Tree
• 재귀함수의 개념

104 Maximum Depth of Binary Tree

문제 해석

이진 트리의 최대 깊이는 루트 노드부터 가장 멀리 있는 리프(leaf) 노드까지의 노드 수를 의미합니다. 즉, 루트 노드에서 가장 아래쪽에 있는 노드까지 가는 경로 중에서 가장 긴 경로의 노드 개수를 구하면 됩니다.

문제 예시

1. 예시 1:
   • 입력: root = [3, 9, 20, null, null, 15, 7]
   • 출력: 3
   • 설명: 이 트리는 다음과 같습니다

    3
   / \
  9  20
     / \
    15  7

2. 예시 2:

• 입력: root = [1, null, 2]
• 출력: 2
• 설명: 이 트리는 다음과 같습니다

    1
     \
      2

문제 풀이 방법

이 문제를 풀기 위해서는 재귀(Recursive) 함수를 사용하는 방법이 효과적입니다. 이진 트리의 각 노드에 대해 왼쪽 자식 노드와 오른쪽 자식 노드의 깊이를 재귀적으로 계산한 다음, 두 깊이 중 더 큰 값에 1을 더하면 현재 노드의 깊이가 됩니다.

코드설명

# 이진 트리의 노드를 나타내는 클래스
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 최대 깊이를 계산하는 함수
def maxDepth(root):
    # 만약 노드가 없으면 깊이는 0
    if root is None:
        return 0
    
    # 왼쪽과 오른쪽 자식 노드의 깊이를 재귀적으로 계산
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    # 현재 노드의 깊이는 자식 노드 깊이 중 큰 값에 1을 더한 값
    return max(left_depth, right_depth) + 1

코드 설명

1. TreeNode 클래스: 이 클래스는 이진 트리의 노드를 나타냅니다. 각 노드는 값(val), 왼쪽 자식 노드(left), 오른쪽 자식 노드(right)를 가집니다.
2. maxDepth 함수: 이 함수는 주어진 이진 트리의 최대 깊이를 계산합니다.
   • 기본 조건: 만약 노드가 없으면(즉, root가 None이면) 깊이는 0입니다.
   • 재귀 호출: 왼쪽 자식 노드와 오른쪽 자식 노드의 깊이를 각각 재귀적으로 계산합니다.
   • 현재 노드의 깊이 계산: 왼쪽 깊이와 오른쪽 깊이 중 더 큰 값에 1을 더한 값을 반환합니다. 여기서 1을 더하는 이유는 현재 노드 자체도 깊이에 포함되기 때문입니다.

재귀 함수란?

재귀 함수는 자기 자신을 다시 호출하는 함수예요. 좀 더 쉽게 말하면, 함수 안에서 자기 자신을 또 다시 부르는 함수를 재귀 함수라고 해요.

예시로 이해하기

    3
   / \
  9  20
     /  \
    15   7

1. 루트 노드 3에서 maxDepth(3)을 호출해요.
2. maxDepth(3)는 maxDepth(9)와 maxDepth(20)을 호출해요.
3. maxDepth(9)는 자식이 없어서 1을 반환해요.
4. maxDepth(20)는 maxDepth(15)와 maxDepth(7)을 호출해요.
5. maxDepth(15)와 maxDepth(7)은 자식이 없어서 각각 1을 반환해요.
6. maxDepth(20)는 1 + max(1, 1) = 2를 반환해요.
7. 마지막으로 maxDepth(3)는 1 + max(1, 2) = 3을 반환해요.

오늘의 회고

• 이진 검색 트리의 문제에서 최대 깊이의 문제를 풀었다.
• 재귀 함수의 개념에 대해서 익힐수 있었다.
• 코드 리뷰라고 하더라도 문제를 이해하는게 정말 중요함을 느낀다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• LV1의 문제라지만 생각을 많이 하는 문제는 정말 좋은거 같다.

오늘의 공부 키워드

• 이진검색 트리(BST) 구조 반전
• 226 Invert Binary Tree

226 . Invert Binanay Tree

문제 해석

"Binary Tree Invert" 문제는 주어진 이진 트리(Binary Tree)의 구조를 반전시키는 문제입니다. 이진 트리란 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 이 문제에서 반전이란 왼쪽 자식과 오른쪽 자식을 서로 바꾸는 것을 의미합니다.

    4
   / \
  2   7
 / \ / \
1  3 6  9

    4
   / \
  7   2
 / \ / \
9  6 3  1

문제 해결 방법

이 문제를 해결하기 위해, 다음의 단계들을 따릅니다:

1. 기본 아이디어: 트리의 각 노드에 대해, 그 노드의 왼쪽 자식과 오른쪽 자식을 서로 교환합니다.
2. 재귀 함수 사용: 트리 구조는 재귀적으로 정의되므로, 각 노드에 대해 재귀적으로 왼쪽과 오른쪽 자식을 교환하는 방법을 사용할 수 있습니다.

단계별 해결 방법

1. 기본 케이스: 현재 노드가 None인 경우(즉, 트리가 비어 있거나 리프 노드의 자식인 경우), 그대로 None을 반환합니다.
2. 재귀적 호출: 현재 노드의 왼쪽 자식과 오른쪽 자식을 서로 교환하고, 각각의 자식에 대해 다시 이 과정을 재귀적으로 수행합니다.

코드설명

from typing import Optional

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 트리가 비어 있는 경우
        if root is None:
            return None
        
        # 왼쪽과 오른쪽 자식을 교환합니다.
        root.left, root.right = root.right, root.left
        
        # 재귀적으로 각 자식에 대해 invertTree를 호출합니다.
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

코드 설명

1. 주어진 이진 트리가 비어 있는지 확인합니다. 비어 있다면 None을 반환합니다.
2. 현재 노드의 왼쪽 자식과 오른쪽 자식을 교환합니다.
3. 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 invertTree 메서드를 호출하여 각각의 하위 트리를 반전시킵니다.
4. 최종적으로 반전된 트리의 루트 노드를 반환합니다.

이 알고리즘은 모든 노드에 대해 한 번씩 방문하므로, 시간 복잡도는 O(n)이며, 여기서 n은 트리의 노드 수입니다.

오늘의 회고

• 이진 검색 트리의 문제가 정말 많다는걸 느꼈다.
• 이진 검색 트리를 정말 잘 익혀야 한다는 생각이 든다.
• 여전히 개념에 대한 이해가 안되어 코드 리뷰 수준으로 문제를 푼점은 다시한번 아쉽게 된다.
• 그래도 이렇게 기록으로 남기는건 나중에 다시한번 풀어보려는 이유 및
    어떻게 풀었는지 알기 위해서 기록을 남긴다.
• LV1의 문제라지만 생각을 많이 하는 문제는 정말 좋은거 같다.