문제50: 정렬된 배열의 이진 탐색 트리 변환

문제

• 높이 균형이란 모든 노드의 두 서브 트리 간 깊이 차이가 1이하인 것을 말한다.

입력

[-10,-3,0,5,9]

출력

[0,-3,9,-10,null,5]

풀이

1. 정렬된 배열을 이진 검색으로 쪼개나간다. (이진 검색 결과로 트리 구성)
1. 배열이 정렬되어 있어야 한다.
1. 배열된 정렬의 탐색은 log(n)

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

새로운 개념