두 개의 이진 트리(binary tree)가 주어졌을 때, 두 트리가 구조와 값 모든 면에서 완전히 동일한지 확인해야 하는 경우가 있습니다. 이렇게 서로 똑같은 트리를 흔히 쌍둥이 트리(twin trees)라고 부릅니다.
예를 들어 아래와 같은 트리 쌍이 입력으로 주어진다면, 첫 번째 쌍은 구조와 값이 모두 일치하므로 True가 출력됩니다. 반면 두 번째 쌍은 노드의 값이 다르고, 세 번째 쌍은 트리의 구조 자체가 달라서 각각 False가 출력됩니다.
문제 해결 접근 방식
이 문제는 재귀(recursion)를 활용하면 깔끔하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 두 개의 루트 노드를 인자로 받는
solve()메서드를 정의합니다. root0과root1이 모두 null(비어 있는 노드)이라면 두 트리가 해당 위치에서 동일하다는 의미이므로True를 반환합니다.root0또는root1중 하나만 null이라면 한쪽에만 노드가 존재하는 것이므로 구조가 다르고, 따라서False를 반환합니다.- 두 노드의 값이 서로 다르면
False를 반환합니다. - 위 조건들을 모두 통과했다면, 왼쪽 서브트리끼리(
solve(root0.left, root1.left))와 오른쪽 서브트리끼리(solve(root0.right, root1.right))를 재귀적으로 비교한 결과가 모두 참일 때True를, 하나라도 거짓이면False를 반환합니다.
이제 실제 파이썬 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def solve(self, root0, root1):
if not root0 and not root1:
return True
if not root0 or not root1:
return False
if root0.val != root1.val:
return False
return self.solve(root0.left, root1.left) and self.solve(root0.right, root1.right)
ob = Solution()
root1 = TreeNode(10)
root1.left = TreeNode(5)
root1.right = TreeNode(15)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(8)
root2 = TreeNode(10)
root2.left = TreeNode(5)
root2.right = TreeNode(15)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(8)
print(ob.solve(root1, root2))
입력
root1 = TreeNode(10) root1.left = TreeNode(5) root1.right = TreeNode(15) root1.left.left = TreeNode(3) root1.left.right = TreeNode(8) root2 = TreeNode(10) root2.left = TreeNode(5) root2.right = TreeNode(15) root2.left.left = TreeNode(3) root2.left.right = TreeNode(8)
출력
True
동작 원리 정리
위 코드는 두 트리를 루트에서 리프까지 동시에 순회하며 비교합니다. 시간 복잡도는 두 트리 중 작은 쪽의 노드 수에 비례하는 O(n)이며, 재귀 호출 깊이만큼의 공간이 추가로 필요합니다. 값이나 구조가 처음으로 달라지는 지점에서 즉시 False를 반환하므로 불필요한 탐색을 줄일 수 있다는 장점도 있습니다.