[Leetcode] #108. Convert Sorted Array to Binary Search Tree

문제 : Given an integer array nums where the elements are sorted in ascending order, convert it to a 
height-balanced binary search tree.

 

여기서 말하는 height-balanced는  이진 트리의 한 종류로, 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1 이하인 트리를 의미한다.

 

 

 

# 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

        mid = len(nums) // 2
        root = TreeNode(nums[mid])

        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

처음 생각 : 

 

- 루트 노드를 어떤 기준으로 정하지? : 루트 노드는 주어진 리스트에서 중간값으로 정해준다. 왜냐하면 주어진 리스트는 오름차순으로 정렬된 리스트이므로 정확히 중간값을 루트로 정해주면, 리스트의 왼쪽 하위 요소들은 left-subtree가 되고, 오른쪽 하위 요소들은 right-subtree가 된다. 

 

- 자 그러면, 루트를 정했다고 치자. 그러면 왼쪽 서브트리와 오른쪽 서브트리는 어떻게 채워 나가지? 생각해보면 이미 루트값은 맨 처음에 정해지고, 왼쪽, 오른쪽 서브트리를 채워나가면 되므로 뭔가 분할정복 + 재귀가 떠올랐다.

 

위의 예시 nums = [-10, -3, 0, 5, 9]를 보면, 

 

1. 최상단 루트노드의 값은 몫 연산자(//)를 사용하여 정수 뒤의 소수점을 버리고 가운데 값을 루트 노드로 정한다. 이 경우, '0'이 루트 노드가 되는것! 그 다음, 0의 왼쪽값 [-10, -3]은 왼쪽 서브트리의 요소들이 될 것이고, 오른쪽 값[5, 9]는 오른쪽 서브트리의 값이 될것이다.

 

2. 그러면 서브트리에도 똑같은 로직을 취해주면 원하는대로 완성되는가? 예를들어, 리스트의 왼쪽 하위 요소들에 대해 1. 과 같은 로직을 취하면, [-10, -3]의 중간값은 2 // 2 = 1 이므로 -3이다. 또다시 왼쪽 하위요소인 [-10]에 대해 똑같은 로직을 수행하면 mid값은 0이 될것이다(1 // 2). 결국 -10이 루트 노드가 될것이고, 이런 식으로 왼쪽, 오른쪽을 분할정복 + 재귀를 통해 풀어 나갈 수 있다.

 

※ 몰랐던 내용이나 까먹었었던 내용 : 

 

파이썬에서 클래스 메서드를 호출할 때 `self`를 사용하는 이유는 그 메서드가 클래스의 인스턴스 메서드임을 나타내기 위해서이다. `self`는 인스턴스 자신을 참조하는 변수로, 클래스 내에서 정의된 메서드나 속성에 접근할 때 사용된다.

`self.`를 사용하는 이유:

1. 인스턴스 메서드 호출:
   클래스 내에서 메서드를 정의할 때, 그 메서드가 인스턴스 메서드임을 나타내기 위해 첫 번째 인자로 `self`를 받는다. 이를 통해 메서드 내에서 인스턴스 속성에 접근하거나 다른 인스턴스 메서드를 호출할 수 있다.

2. 클래스 내에서 재귀 호출:
   인스턴스 메서드가 재귀적으로 자기 자신을 호출하려면 `self`를 사용하여 현재 인스턴스의 메서드를 호출해야 한다. 이렇게 하면 클래스의 다른 인스턴스 메서드와 구분된다.

예를 들어, 주어진 `sortedArrayToBST` 메서드에서 `self.sortedArrayToBST`를 사용하는 이유는 현재 인스턴스의 메서드를 호출하기 위해서이다. 이렇게 하면 재귀 호출이 가능해진다.

예시 : 

class Example:
    def __init__(self, value):
        self.value = value

    def display(self):
        print(self.value)
    
    def increment(self):
        self.value += 1
        self.display()  # self를 사용하여 다른 인스턴스 메서드를 호출

    def recursive_example(self, n):
        if n > 0:
            print(n)
            self.recursive_example(n - 1)  # self를 사용하여 재귀 호출

# 클래스 인스턴스 생성
example = Example(10)

# 인스턴스 메서드 호출
example.increment()  # 출력: 11

# 재귀 메서드 호출
example.recursive_example(5)  # 출력: 5, 4, 3, 2, 1

이 예제에서:
- `self.display()`는 `increment` 메서드 내에서 `display` 메서드를 호출한다.
- `self.recursive_example(n - 1)`은 `recursive_example` 메서드 내에서 재귀적으로 자기 자신을 호출한다.

따라서, `self.`를 사용하는 것은 인스턴스 메서드를 호출할 때 그 메서드가 현재 인스턴스에 속해 있음을 명확히 하기 위해 필요하다.