50. Convert Sorted Array to Binary Search Tree

🎯 leetcode - 108. Convert Sorted Array to Binary Search Tree

---

📌 문제

- 파이썬 알고리즘 인터뷰 50번 문제
- 정렬된 리스트를 이진 탐색 트리로 변환하기

📌 날짜

2020.02.21

📌 시도 횟수

2 try / Failed

💡 Code

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        mid = len(nums) // 2
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid + 1 :])

        return node

💡 문제 해결 방법

1. 현재 노드는 리스트의 중앙값이 되어야 한다.
2. 중앙값을 기준으로 리스트를 노드의 왼쪽, 오른쪽으로 나눈다.
> 1, 2를 계속 반복(더이상 슬라이싱 할수 있는 리스트가 없을때까지)

💡 새롭게 알게 된 점

✔ // 연산자 : /(나눗셈)한 결과의 내림값을 리턴한다.
✔ 높이 균형 이진 탐색 트리의 루트는 정렬된 배열의 '중앙값'이 되어야 한다.

• 높이 균형 이진탐색트리 예시
  

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 높이 균형 이진 탐색 트리에 대한 이해가 부족했다.