문제 소개
이진 트리(binary tree)가 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 트리 안에서 이진 탐색 트리(BST, Binary Search Tree)의 성질을 만족하는 가장 큰 하위 트리를 찾아내고, 해당 BST의 루트 노드를 반환하는 것입니다.
예를 들어 위와 같은 트리가 입력으로 주어지면 출력은 다음과 같습니다.
해결 접근 방식: 단계별 알고리즘
이 문제는 후위 순회(post-order traversal) 기반의 재귀 함수를 사용하면 효율적으로 해결할 수 있습니다. 각 노드에서 왼쪽과 오른쪽 자식의 결과를 먼저 계산한 뒤, 현재 노드가 BST의 값 규칙을 만족하는지 확인하는 구조입니다. 구체적인 단계는 다음과 같습니다.
- 변수
c:= 0 으로 초기화합니다. (현재까지 발견한 최대 BST의 노드 수) - 변수
m:= null 로 초기화합니다. (가장 큰 BST의 루트 노드) - 노드를 인자로 받는 재귀 함수
recurse()를 정의합니다.- node가 null이 아니라면 다음을 수행합니다.
left_val := recurse(node.left): 왼쪽 서브트리의 BST 노드 수right_val := recurse(node.right): 오른쪽 서브트리의 BST 노드 수count:= 음의 무한대(-∞)로 초기화- (node.left가 null이거나
node.left.val <= node.val)이면서 (node.right가 null이거나node.val <= node.right.val)인 경우, 즉 현재 노드가 BST 규칙을 만족하면:count := left_val + right_val + 1
count > c라면 최댓값을 갱신합니다:c := count,m := node
count를 반환합니다.
- node가 null이면 0을 반환합니다.
- node가 null이 아니라면 다음을 수행합니다.
- 루트 노드로
recurse(root)를 호출한 뒤m을 반환합니다.
파이썬 구현 예제
다음 코드를 통해 동작 방식을 더 잘 이해해 보겠습니다.
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
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 print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end = ', ')
print_tree(root.right)
def solve(root):
c, m = 0, None
def recurse(node):
if node:
nonlocal c, m
left_val = recurse(node.left)
right_val = recurse(node.right)
count = -float("inf")
if (node.left == None or node.left.val <= node.val) and (node.right == None or node.val <= node.right.val):
count = left_val + right_val + 1
if count > c:
c = count
m = node
return count
return 0
recurse(root)
return m
tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))
실행 결과 확인
입력
tree = make_tree([1, 4, 6, 3, 5]) print_tree(solve(tree))
출력
3, 4, 5,
동작 원리와 시간 복잡도
입력 트리 [1, 4, 6, 3, 5]는 다음과 같은 구조를 가집니다. 루트 1의 왼쪽 자식은 4, 오른쪽 자식은 6이며, 노드 4의 왼쪽 자식은 3, 오른쪽 자식은 5입니다.
전체 트리는 루트 1의 왼쪽 자식 값(4)이 부모 값(1)보다 커서 BST 규칙을 위반하므로 BST가 아닙니다. 반면 노드 4를 루트로 하는 하위 트리는 왼쪽 자식(3) ≤ 부모(4) ≤ 오른쪽 자식(5)의 BST 조건을 완벽하게 만족하며, 총 3개의 노드로 구성된 가장 큰 BST입니다. 따라서 중위 순회(in-order) 결과로 3, 4, 5,가 출력되는 것입니다.
이 알고리즘은 모든 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 스택의 깊이는 트리의 높이 h에 비례하여 공간 복잡도는 O(h)입니다.