이진 트리가 하나 주어졌을 때, 해당 트리가 대칭 트리(symmetric tree)인지 확인해야 합니다. 대칭 트리란 자기 자신의 거울상(mirror image)과 완전히 동일한 트리를 의미합니다. 예를 들어 좌우로 접었을 때 완벽하게 겹치는 나무 구조를 상상하면 이해하기 쉽습니다. 두 개의 트리를 비교했을 때 첫 번째 트리는 대칭이지만, 두 번째 트리는 대칭이 아닙니다.
문제 해결 접근 방법
이 문제는 재귀(Recursion)를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 트리의 왼쪽 부분과 오른쪽 부분을 교차하여 비교하는 것입니다. 즉, 왼쪽 서브트리의 왼쪽 자식은 오른쪽 서브트리의 오른쪽 자식과, 왼쪽 서브트리의 오른쪽 자식은 오른쪽 서브트리의 왼쪽 자식과 각각 일치해야 합니다.
다음 단계를 순서대로 따릅니다.
solve(root, root)형태로 함수를 호출하고, 이후 단계들을 재귀적으로 수행합니다.node1과node2가 모두 비어 있다면(None이라면)True를 반환합니다. 양쪽 모두 자식이 없다는 것은 대칭에 위배되지 않기 때문입니다.node1또는node2중 하나만 비어 있다면False를 반환합니다. 한쪽에만 자식이 존재하면 대칭이 아니기 때문입니다.node1.data == node2.data이고,solve(node1.left, node2.right)와solve(node1.right, node2.left)가 모두 참일 때True를 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution(object):
def isSymmetric(self, root):
return self.solve(root, root)
def solve(self, node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return (node1.data == node2.data and
self.solve(node1.left, node2.right) and
self.solve(node1.right, node2.left))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
ob1 = Solution()
print(ob1.isSymmetric(root))
입력
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
출력
True
위 예제에서 루트 노드의 값은 1이고, 왼쪽 서브트리(2 → 3, 4)와 오른쪽 서브트리(2 → 4, 3)가 거울상 관계를 이루므로 결과는 True입니다.
복잡도 분석
- 시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이(h)에 비례합니다. 균형 잡힌 트리라면 O(log n)입니다.