공부블로그

오늘의 공부 키워드

• 이진검색 트리(BST)
• Leetcode 938 Range Sum of BST

이진 검색 트리란?

이진 검색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 검색 트리에서는 다음과 같은 규칙이 있습니다:

1. 왼쪽 자식 노드는 항상 부모 노드보다 값이 작습니다.
2. 오른쪽 자식 노드는 항상 부모 노드보다 값이 큽니다.

LeetCode 938 Range Sum of BST

문제설명

주어진 이진 검색 트리에서 low와 high라는 두 정수가 주어졌을 때, 이 범위 내에 있는 모든 노드의 값의 합을 구하는 문제입니다.

예시 1:

• 트리: [10, 5, 15, 3, 7, null, 18]
• 범위: [7, 15]
• 결과: 32 (7 + 10 + 15)

예시 2:

• 트리: [10, 5, 15, 3, 7, 13, 18, 1, null, 6]
• 범위: [6, 10]
• 결과: 23 (6 + 7 + 10)

해결 방법

이 문제를 해결하기 위해서는 트리를 탐색하면서 각 노드의 값을 확인해야 합니다. 이진 검색 트리의 특성을 활용하면 효율적으로 탐색할 수 있습니다. 예를 들어, 현재 노드의 값이 low보다 작으면 왼쪽 서브트리에는 low 이상인 값이 없으므로 오른쪽 서브트리만 탐색하면 됩니다. 마찬가지로, 현재 노드의 값이 high보다 크면 오른쪽 서브트리에는 high 이하인 값이 없으므로 왼쪽 서브트리만 탐색하면 됩니다.

이를 구현하는 간단한 알고리즘은 다음과 같습니다:

1. 노드가 null이면 0을 반환합니다.
2. 현재 노드의 값이 low보다 작으면 오른쪽 서브트리로 이동합니다.
3. 현재 노드의 값이 high보다 크면 왼쪽 서브트리로 이동합니다.
4. 현재 노드의 값이 low와 high 사이에 있으면 현재 노드의 값과 왼쪽, 오른쪽 서브트리의 값을 더합니다.

코드

from typing import Optional

# TreeNode 클래스 정의
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Solution 클래스 정의
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        # 노드가 None인 경우 0 반환
        if not root:
            return 0
        
        # 노드의 값이 low보다 작으면 오른쪽 서브트리 탐색
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        
        # 노드의 값이 high보다 크면 왼쪽 서브트리 탐색
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        
        # 노드의 값이 범위 내에 있으면 현재 노드의 값 + 왼쪽 서브트리 + 오른쪽 서브트리 값 반환
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

# 사용 예시
if __name__ == "__main__":
    # 예제 트리 구성
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(15)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(18)

    # Solution 객체 생성
    solution = Solution()

    # 범위 [7, 15]에 대한 합 계산
    result = solution.rangeSumBST(root, 7, 15)
    print(result)  # 출력: 32

코드 설명

1. TreeNode 클래스 정의: 트리 노드를 나타내는 클래스를 정의합니다. 각 노드는 값(val), 왼쪽 자식(left), 오른쪽 자식(right)을 가집니다.
2. Solution 클래스 정의: rangeSumBST 메서드를 포함하는 클래스를 정의합니다.
   • rangeSumBST 메서드는 재귀적으로 트리를 탐색하여 범위 내의 노드 값들을 더합니다.
   • 노드가 None인 경우 0을 반환합니다.
   • 현재 노드의 값이 low보다 작으면 오른쪽 서브트리를 탐색합니다.
   • 현재 노드의 값이 high보다 크면 왼쪽 서브트리를 탐색합니다.
   • 현재 노드의 값이 범위 내에 있으면 현재 노드의 값과 왼쪽, 오른쪽 서브트리의 값을 더합니다.
3. 사용 예시: 예제 트리를 구성하고, Solution 객체를 생성하여 rangeSumBST 메서드를 호출하여 결과를 출력합니다.

오늘의 회고

• 이진 검색 트리라는 새로운 개념을 알수 있어서 좋았다.
• 개념을 몰라 어떻게 풀지 고민하다가 chat gpt를 사용하여 문제를 풀었고 코드 리뷰를 통해 익히는 방법으로 하였다.
• 아직 python에 대해 모르는 문제가 많고 바로바로 문제를 어떻게 풀지 모르겠어서 고민이긴 하다.
• 내일은 codeup에서 계속 기초를 다지기 위해 기초 문제를 푸는중인데 그걸 집중적으로 더 풀고 프로그래머스로
  넘어가고 싶다.