문제 개요
하나의 이진 트리가 주어졌을 때, 그 안에서 노드 수가 가장 많은 하위 트리 중 이진 탐색 트리(Binary Search Tree, BST)의 조건을 만족하는 것을 찾아야 합니다.
예를 들어 다음과 같은 입력 트리가 있다고 가정해 보겠습니다.
이 경우 출력 결과는 다음과 같습니다.
해결 접근 방법
이 문제는 후위 순회(post-order traversal)를 활용해 해결할 수 있습니다. 각 노드에 대해 왼쪽과 오른쪽 서브트리의 값을 모두 수집한 뒤, 해당 목록이 정렬되어 있는지 확인하면 그 하위 트리가 BST인지 판별할 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- max_size := [0], max_node := [null] 로 초기화합니다.
- traverse(node) 함수를 정의합니다.
- node가 null이면 빈 리스트를 반환합니다.
- left := traverse(node.left), right := traverse(node.right) 를 재귀적으로 호출합니다.
- lst := left + [node.val] + right 로 현재 노드를 포함한 전체 값 목록을 만듭니다.
- lst가 오름차순으로 정렬되어 있다면 해당 하위 트리는 BST입니다. 이때 max_size보다 lst의 크기가 크면 max_size와 max_node를 갱신합니다.
- lst를 반환하고, 루트에서 traverse(root)를 호출한 뒤 최종적으로 max_node[0]을 반환합니다.
Python 구현 예제
다음 코드를 통해 더 자세히 이해해 보겠습니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end=', ')
print_tree(root.right)
class Solution:
def solve(self, root):
max_size = [0]
max_node = [None]
def traverse(node):
if not node:
return []
left = traverse(node.left)
right = traverse(node.right)
lst = left + [node.val] + right
if sorted(lst) == lst:
if max_size[0] < len(lst):
max_size[0] = len(lst)
max_node[0] = node
return lst
traverse(root)
return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))입력
root = TreeNode(12) root.left = TreeNode(3) root.right = TreeNode(5) root.right.left = TreeNode(4) root.right.right = TreeNode(6)
출력
4, 5, 6,
동작 원리 설명
위 예제에서 루트 노드 12를 포함한 전체 트리는 BST 조건(왼쪽 자식 < 부모 < 오른쪽 자식)을 만족하지 않습니다. 반면 노드 5를 루트로 하는 하위 트리는 4 < 5 < 6 으로 BST 조건을 충족하며, 노드 3개로 구성된 가장 큰 BST 하위 트리입니다. 따라서 중위 순회 결과인 4, 5, 6,이 출력됩니다.
참고로 이 방식은 각 노드마다 리스트를 병합하고 정렬 여부를 검사하기 때문에 시간 복잡도는 O(n²)에 가깝습니다. 노드 수가 매우 많은 경우에는 각 서브트리마다 (최솟값, 최댓값, 노드 수, BST 여부) 정보를 함께 반환하는 최적화 기법(O(n))을 사용하는 것이 좋습니다.