[leetcode] 108. Convert Sorted Array to Binary Search Tree

문제 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

---

오름차순 정렬된 nums 배열이 주어질 때, height-balanced BST로 변형하라.

height-balanced BST는 모든 노드들의 두 하위 트리깊이가 1이상 차이가 나지 않는 이진 트리이다.

---

height-balanced BST가 뭔가 했더니

이런식으로 불균형적인 트리를 만들지말란 의미였다. [그림 1]에서 왼쪽 하위트리의 높이는 1, 오른쪽 하위트리의 높이는 3 이므로 1 이상 차이가 나서 높이 균형 BST가 아니다.

결국 노드들을 왼쪽 오른쪽 균등하게 분배하면서 bst를 만들라는 뜻이다.

 

정렬된 nums 배열의 중간 값을 현재 노드로 만들고 중간 값을 기준으로 왼쪽 배열값들은 왼쪽 하위 노드, 오른쪽 배열값들은 오른쪽 하위 노드들로 재귀호출을 해가면서 이진 트리를 만들면 정답이 된다.

 

시간복잡도는 O(N). N = |nums|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/108.%20Convert%20Sorted%20Array%20to%20Binary%20Search%20Tree.cpp