[알고리즘] Leetcode #108 정렬된 배열의 이진 탐색 트리 변환 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

입출력 예

Example 1:

Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3] Output: [3,1] Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

 

Constraints

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

 

Code

def sortedArrayToBST():
    if not nums:
        return None
    
    mid = len(nums) // 2 # 내림값 리턴
    
    #분할 정복으로 구현
    node = TreeNode(num[mid]) # 중앙에 있는 값들 차례로 할당
    node.left = self.sortedArraryToBST(nums[:mid]) # 오름차순 정렬이므로 작은 값
    node.right = self.sortedArrayToBST(nums[mid + 1:]) # 오름차순 정렬이므로 큰 값
    
    return node

높이 균형 BST (이진 탐색 트리)는 서브트리 간 깊이 차이가 1 이하인 트리를 말한다. 오름차순으로 정렬된 리스트를 받아 이를 높이 균형 BST로 만드려면 리스트 내의 중앙값을 찾아 왼쪽 서브트리엔 작은 값을, 오른쪽 서브트리엔 큰 값을 할당하는 식으로 처리할 수 있다. 이때, 서브트리의 균형을 맞추기 위해 재귀로 함수를 호출하여 계속해서 중앙에 있는 값을 찾도록 한다. 이때, 홀수 개의 리스트에 대해 정확히 중앙값으로 맞춰주기 위해 '//' 연산으로 내림 값을 받는다.