문제 설명
BST(이진 탐색 트리)와 두 값 low, high가 주어졌을 때, [low, high] 범위(양 끝값 포함)에 속하지 않는 모든 노드를 삭제하는 것이 목표입니다.
예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.
여기서 low = 7, high = 10이라면, 범위를 벗어나는 노드들이 제거되어 다음과 같은 결과가 나옵니다.
해결 접근 방법
이 문제는 재귀를 활용하면 깔끔하게 해결할 수 있습니다. BST의 핵심 성질, 즉 왼쪽 서브트리의 모든 값은 부모보다 작고 오른쪽 서브트리의 모든 값은 부모보다 크다는 특성을 이용하면 범위를 벗어난 서브트리 전체를 한 번에 잘라낼 수 있습니다.
해결 과정은 다음과 같습니다.
solve(root, low, high)함수를 정의합니다.- root가 null이면 그대로 return합니다.
- low > root.data인 경우: 왼쪽 서브트리 전체가 범위보다 작으므로, 오른쪽 서브트리만 재귀적으로 처리한 결과를 반환합니다.
- high < root.data인 경우: 오른쪽 서브트리 전체가 범위보다 크므로, 왼쪽 서브트리만 재귀적으로 처리한 결과를 반환합니다.
- 노드가 범위 내에 있는 경우: 왼쪽과 오른쪽 자식을 각각 solve()로 재귀적으로 정리한 뒤, 그 결과를 자식 포인터에 다시 연결합니다.
- 최종적으로 root를 반환합니다.
Python 구현 예제
아래 코드를 통해 구현 방법을 자세히 살펴보겠습니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
class Solution:
def solve(self, root, low, high):
if not root:
return
if low > root.data:
return self.solve(root.right, low, high)
if high < root.data:
return self.solve(root.left, low, high)
root.right = self.solve(root.right, low, high)
root.left = self.solve(root.left, low, high)
return root
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
low = 7
high = 10
ret = ob.solve(root, low, high)
print_tree(ret)
입력
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) low = 7 high = 10
출력
7, 8, 9, 10,
복잡도 분석
시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 수로, 각 노드를 최대 한 번씩만 방문하기 때문입니다. 공간 복잡도는 재귀 호출 스택에 의해 결정되며 트리의 높이에 비례하므로, 균형 잡힌 트리에서는 O(log n), 최악의 경우(편향된 트리)에는 O(n)이 됩니다.