108. Convert Sorted Array to Binary Search Tree ☆

108. Convert Sorted Array to Binary Search Tree

 

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 오름차순으로 정렬된 리스트로부터 , 이진 바이너리 서치 트리로 바꿔라 BST
        """
        # base case !! 꼭 있어야!!
        """
        if not nums:
            return None

        root_i = len(nums)//2
        root = TreeNode(nums[root_i])
        root.left = self.sortedArrayToBST(nums[:root_i])
        root.right = self.sortedArrayToBST(nums[root_i+1:])
        return root

 

 

이 문제는 정렬된 정수 배열(nums)이 주어질 때, 이를 사용하여 **높이 균형 이진 탐색 트리(Height-Balanced BST)**를 생성하라는 요청입니다.

---

주요 용어와 개념

1. 이진 탐색 트리(Binary Search Tree, BST):
   • 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
   • BST의 특징:
     • 왼쪽 서브트리의 모든 값은 부모 노드보다 작음.
     • 오른쪽 서브트리의 모든 값은 부모 노드보다 큼.
2. 높이 균형 트리(Height-Balanced):
   • 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리.
   • 트리가 균형 잡혀 있어야, 검색 및 삽입 연산이 효율적으로 이루어짐.

---

문제의 요구사항

• 정렬된 배열 nums를 입력으로 받아, 이를 사용하여 높이 균형 BST를 생성해야 합니다.
• 높이 균형 조건을 만족하는 BST는 여러 가지가 있을 수 있습니다. 문제에서는 그 중 하나를 반환하면 됩니다.

문제의 핵심 질문

1. 정렬된 배열을 어떻게 높이 균형 BST로 변환할 것인가?
   • 트리의 중간 값을 루트로 선택하면 균형을 잡기 쉬움.
   • 왼쪽 절반은 왼쪽 서브트리, 오른쪽 절반은 오른쪽 서브트리로 사용.
2. 트리 생성 순서는 어떻게 결정하는가?
   • 재귀적으로 배열을 분할하며 트리를 생성.
3. 여러 가능한 BST 중 하나만 반환해도 되는가?
   • 예, 높이 균형 조건을 만족하는 트리라면 어떤 형태든 가능합니다.

---

문제 풀이 아이디어

1. 중간값 선택:
   • 배열의 중간 값을 트리의 루트로 설정.
   • 배열을 두 부분으로 나누어 왼쪽과 오른쪽을 각각 서브트리로 사용.
2. 재귀적 접근:
   • 배열이 비어 있으면 null을 반환.
   • 중간 값을 계산하고, 해당 값을 루트로 하는 트리를 생성.
   • 왼쪽 부분은 왼쪽 서브트리, 오른쪽 부분은 오른쪽 서브트리로 연결.

# 이진 트리의 노드를 정의하는 클래스
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val  # 노드의 값
#         self.left = left  # 왼쪽 자식 노드
#         self.right = right  # 오른쪽 자식 노드

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 배열이 비어 있는 경우 (재귀의 끝 조건)
        if not nums:
            return None

        # 배열의 중간 인덱스를 계산 (중간 값이 루트 노드가 됨)
        mid = len(nums) // 2  # 예: nums = [1, 2, 3] -> mid = 1 (값은 nums[1] = 2)

        # 현재 중간 값을 사용하여 루트 노드 생성
        node = TreeNode(nums[mid])

        # 중간 값의 왼쪽 배열로 왼쪽 서브트리 생성
        node.left = self.sortedArrayToBST(nums[:mid])  # nums[:mid]는 중간 값 앞의 배열

        # 중간 값의 오른쪽 배열로 오른쪽 서브트리 생성
        node.right = self.sortedArrayToBST(nums[mid+1:])  # nums[mid+1:]는 중간 값 뒤의 배열

        # 현재 생성된 트리 노드를 반환
        return node

 

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums: # 비어있으면 
            return None

        # 중심값이 root
        m = len(nums)//2
        node = TreeNode(nums[m]) # root 생성하고        
        node.left = self.sortedArrayToBST(nums[:m]) # 왼쪽 배열 넣어서 왼쪽 노드 생성
        node.right = self.sortedArrayToBST(nums[m+1:]) # 오른쪽 배열 넣어서 오른쪽 노드 생성

        return node

 

내 코드

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 리스트를 Tree 로 변경
        if not nums:
            return None # 없으면 

        # 루트 찾아서
        root_i = len(nums)//2
        root = TreeNode(nums[root_i])
        root.left = self.sortedArrayToBST(nums[:root_i])
        root.right = self.sortedArrayToBST(nums[root_i+1:])
        return root