두 개의 이진 트리가 주어졌을 때, 두 번째 트리가 첫 번째 트리의 하위 트리(subtree)에 해당하는지 판별하는 문제입니다. 하위 트리란 어떤 노드를 루트로 삼는 부분 트리가, 대상 트리와 구조 및 노드 값 모두에서 완전히 일치하는 경우를 의미합니다.
예를 들어 아래와 같은 두 트리가 있다고 가정해 보겠습니다.
두 번째 트리는 첫 번째 트리의 노드 4를 루트로 하는 부분과 정확히 일치하므로, 결과는 True가 됩니다.
접근 방법
이 문제는 재귀(recursion)를 활용하면 깔끔하게 해결할 수 있습니다. 알고리즘은 다음 단계로 진행됩니다.
solve(root, target)함수를 정의합니다.- root와 target이 모두 null(None)이면 True를 반환합니다.
- 둘 중 하나만 null이면 False를 반환합니다.
- 두 노드의 값이 같다면, 왼쪽 자식끼리·오른쪽 자식끼리 각각 재귀 비교한 결과를 논리곱(AND)으로 반환합니다.
- 값이 다르다면, root의 왼쪽 또는 오른쪽 서브트리에서 target과 일치하는 시작점을 찾기 위해 논리합(OR)으로 탐색을 계속합니다.
아래 예제 코드를 통해 자세히 살펴보겠습니다.
예제 코드
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root, target):
# 두 노드가 모두 None이면 구조가 일치
if root is None and target is None:
return True
# 한쪽만 None이면 일치하지 않음
if root is None or target is None:
return False
if root.val == target.val:
return (self.solve(root.left, target.left) and
self.solve(root.right, target.right))
else:
return (self.solve(root.left, target) or
self.solve(root.right, target))
ob = Solution()
root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)
print(ob.solve(root1, root2))
입력
root1 = TreeNode(6) root1.left = TreeNode(4) root1.right = TreeNode(10) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5) root2 = TreeNode(4) root2.left = TreeNode(3) root2.right = TreeNode(5)
출력
True
동작 원리
먼저 첫 번째 트리의 루트 노드 6과 target의 루트 4를 비교합니다. 값이 다르므로 왼쪽 서브트리에서 일치하는 시작점을 찾습니다. 노드 4에서 값이 일치하고, 자식 노드 3과 5 역시 target과 동일하므로 최종적으로 True가 반환됩니다.
복잡도 분석
- 시간 복잡도: 최악의 경우 O(n × m). n은 첫 번째 트리의 노드 수, m은 두 번째 트리의 노드 수입니다.
- 공간 복잡도: 재귀 호출 스택으로 인해 최대 O(h). h는 트리의 높이입니다.
참고: 더 견고한 구현
위 구현은 현재 노드에서 값이 일치했는데 자식 비교가 실패하면, 다른 후보 위치를 다시 시도하지 않는 한계가 있습니다. 트리 안에 같은 값을 가진 노드가 여러 개 존재할 수 있다면, 다음처럼 '일치 검사'와 '탐색'을 분리하는 것이 안전합니다.
class Solution:
def is_subtree(self, root, target):
if target is None:
return True
if root is None:
return False
if self.is_same(root, target):
return True
return (self.is_subtree(root.left, target) or
self.is_subtree(root.right, target))
def is_same(self, a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return (a.val == b.val and
self.is_same(a.left, b.left) and
self.is_same(a.right, b.right))
이렇게 구현하면 하위 트리가 어느 위치에서 시작하더라도 정확하게 판별할 수 있습니다.