[Leet code] 108. Convert Sorted Array to Binary Search Tree

Tag	자료구조
Tags	bst
사이트	Leet code
이해	완벽히 이해
난이도	★
메모	bst 와 이진 검색
발행 여부
최종 편집 일시	@2021년 12월 29일 오후 10:20
푼 날짜	@2021년 12월 29일 오후 10:08
Category	ps/자료구조

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

풀이 코드 (책)

퇴고

문제 해설 및 주의사항

원문

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.

번역 및 주의사항

• nums : 오름차순으로 정렬된 배열
  • 자식 트리의 높이 차이가 1 이하인 것이 높이 균형 BST 이다.
  • nums 를 높이 균형 BST 로 변환하라.

---

풀이

• BST 의 특징을 이용하자.
  • 정렬된 배열에 대해서 이진 검색으로 계속 쪼개나가면 BST 를 만들 수 있다.

풀이 코드 (책)

# 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

        mid_node = TreeNode(nums[mid])
        mid_node.left = self.sortedArrayToBST(nums[:mid])
        mid_node.right = self.sortedArrayToBST(nums[mid+1:])
        
        return mid_node

• mid 가 현재 배열의 중간 인덱스를 가진다.
  • mid_node 가 현재 배열의 중간 node 를 의미한다.
  • mid_node 의 left node : 현재 배열의 중간 전까지의 재귀
  • mid_node 의 right node : 현재 배열의 중간 이후부터 재귀

---

퇴고