문제 개요
정렬된 배열 A가 하나 주어져 있을 때, 이를 높이 균형(height-balanced) 이진 탐색 트리로 변환해야 합니다. 여기서 높이 균형 이진 트리란, 모든 노드에 대해 왼쪽 하위 트리와 오른쪽 하위 트리의 깊이 차이가 절대 1을 초과하지 않는 이진 트리를 의미합니다.
예를 들어 배열이 [-10, -3, 0, 5, 9]라고 한다면, 가능한 출력 결과 중 하나는 다음과 같은 형태입니다: [0, -3, 9, -10, null, 5]
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 배열 A가 비어 있다면 None을 반환합니다.
- 배열의 중간 원소를 찾아 루트 노드로 만듭니다.
- 중간 원소를 기준으로 배열을 왼쪽 부분 배열과 오른쪽 부분 배열, 두 개로 나눕니다.
- 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 각각 재귀적으로 동일한 작업을 수행합니다.
이 방식이 잘 작동하는 이유는 간단합니다. 정렬된 배열에서 중간값을 루트로 선택하면 왼쪽과 오른쪽에 거의 같은 개수의 원소가 배치되기 때문에, 트리 전체의 높이 균형이 자연스럽게 유지됩니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def height(root):
if root is None:
return 0
else :
# 왼쪽과 오른쪽 하위 트리의 높이를 계산
l_height = height(root.left)
r_height = height(root.right)
# 더 큰 값을 찾아 반환
if l_height > r_height :
return l_height+1
else:
return r_height+1
def print_given_level(root, level):
if root is None:
return
if level == 1:
print(root.data,end = ',')
elif level > 1 :
print_given_level(root.left , level-1)
print_given_level(root.right , level-1)
def level_order(root):
print('[', end = '')
h = height(root)
for i in range(1, h+1):
print_given_level(root, i)
print(']')
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = nums[len(nums)//2]
root = TreeNode(mid)
root.left = self.sortedArrayToBST(nums[:len(nums)//2])
root.right = self.sortedArrayToBST(nums[len(nums)//2 +1 :])
return root
nums = [-10,-3,0,5,9]
ob1 = Solution()
bst = ob1.sortedArrayToBST(nums)
level_order(bst)입력
nums = [-10,-3,0,5,9]
출력
[0,-3,9,-10,5]
핵심 로직은 sortedArrayToBST 메서드에 있습니다. 배열의 중간 인덱스(len(nums)//2)에 해당하는 값을 루트로 삼고, 슬라이싱을 통해 얻은 왼쪽·오른쪽 부분 배열에 대해 자기 자신을 재귀 호출하여 하위 트리를 구성합니다. 이 과정은 시간 복잡도 O(n), 공간 복잡도 O(log n)(재귀 호출 스택 기준)로 효율적으로 동작합니다.