문제 소개
하나의 이진 트리(binary tree)가 주어졌을 때, 왼쪽 서브트리와 오른쪽 서브트리가 완전히 동일한 가장 큰 서브트리를 찾는 문제입니다. 이때 선호되는 시간 복잡도는 O(n)입니다.
예를 들어 아래와 같은 트리가 입력으로 주어진다면,
결과는 다음과 같이 나타납니다.
접근 방법
이 문제는 후위 순회(postorder traversal)를 활용한 재귀적 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 노드를 기준으로 서브트리의 구조와 값을 문자열로 직렬화(인코딩)합니다.
- 왼쪽 서브트리의 인코딩 결과와 오른쪽 서브트리의 인코딩 결과가 일치하면, 해당 노드를 루트로 하는 서브트리는 좌우가 동일한 조건을 만족합니다.
- 조건을 만족하는 서브트리 중 크기가 가장 큰 것을 계속 추적하여 마지막에 반환합니다.
알고리즘 단계
solve() 함수를 정의합니다. 매개변수는 root, encode, maxSize, maxNode입니다.
- root가 None이면 0을 반환합니다.
- left_list와 right_list를 빈 문자열을 담은 리스트로 초기화합니다.
- ls := solve(root.left, left_list, maxSize, maxNode)로 왼쪽 서브트리의 크기를 구하고, rs := solve(root.right, right_list, maxSize, maxNode)로 오른쪽 서브트리의 크기를 구합니다.
- size := ls + rs + 1을 계산합니다.
- left_list[0]과 right_list[0]이 같다면, 즉 좌우 서브트리가 동일하다면 size가 maxSize[0]보다 클 때 maxSize[0] := size, maxNode[0] := root로 갱신합니다.
- encode[0]에 "|" 구분자와 함께 왼쪽 서브트리 인코딩, 현재 노드의 값, 오른쪽 서브트리 인코딩을 차례로 이어 붙입니다.
- size를 반환합니다.
메인 메서드에서는 maximum := [0], encode := 빈 문자열을 담은 리스트를 준비한 뒤 solve(node, encode, maximum, maxNode)를 호출하고, 최종적으로 maximum을 반환합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
class TreeNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
if (root == None):
return 0
left_list = [""]
right_list = [""]
ls = solve(root.left, left_list, maxSize, maxNode)
rs = solve(root.right, right_list, maxSize, maxNode)
size = ls + rs + 1
if (left_list[0] == right_list[0]):
if (size > maxSize[0]):
maxSize[0] = size
maxNode[0] = root
encode[0] = encode[0] + "|" + left_list[0] + "|"
encode[0] = encode[0] + "|" + str(root.data) + "|"
encode[0] = encode[0] + "|" + right_list[0] + "|"
return size
def largestSubtree(node, maxNode):
maximum = [0]
encode = [""]
solve(node, encode, maximum, maxNode)
return maximum
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree", maxNode[0].data)
print("and its size is", maximum)
입력
root = TreeNode(55) root.left = TreeNode(15) root.right = TreeNode(70) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(75) root.right.left.left = TreeNode(65) root.right.left.right = TreeNode(80) root.right.right = TreeNode(75) root.right.right.left = TreeNode(65) root.right.right.right = TreeNode(80)
실행 결과
Root of largest sub-tree 70 and its size is [7]
즉, 값 70을 루트로 하는 서브트리가 왼쪽 서브트리(75 → 65, 80)와 오른쪽 서브트리(75 → 65, 80)가 동일한 크기 7의 가장 큰 서브트리임을 확인할 수 있습니다.
시간 복잡도 참고 사항
위와 같은 문자열 연결 기반의 직렬화 방식은 구현이 직관적이라는 장점이 있지만, 최악의 경우 문자열 비교와 결합 비용 때문에 O(n²)까지 늘어날 수 있습니다. 엄격하게 O(n)의 성능을 보장하려면 각 서브트리에 고유 ID를 부여하고 해시 맵(hash map)으로 관리하는 방식을 사용하는 것이 좋습니다.