대칭 이진 트리란?
하나의 이진 트리가 주어졌을 때, 해당 트리가 대칭(symmetric) 트리인지 판별해야 합니다. 트리를 좌우로 뒤집은 거울상(미러 이미지)이 원래 트리와 완전히 동일할 때, 그 트리를 대칭 트리라고 부릅니다.
예를 들어 아래 두 트리 중 첫 번째 트리는 대칭이지만, 두 번째 트리는 일부 노드의 위치가 어긋나 있어 대칭이 아닙니다.
해결 접근 방법
대칭 여부는 루트의 왼쪽 서브트리와 오른쪽 서브트리를 서로 미러링하며 비교하는 재귀 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- solve(root, root) 형태로 함수를 호출한 뒤, 이후 단계들을 재귀적으로 수행합니다.
- 두 노드(node1, node2)가 모두 비어 있다면 true를 반환합니다.
- 둘 중 하나만 비어 있다면 false를 반환합니다.
- node1의 값과 node2의 값이 같고, 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
def insert(temp, data):
que = []
que.append(temp)
while len(que):
temp = que[0]
que.pop(0)
if not temp.left:
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
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))
tree1 = make_tree([1, 2, 2, 3, 4, 4, 3])
tree2 = make_tree([1, 2, 2, 3, 4, None, 3])
ob1 = Solution()
print(ob1.isSymmetric(tree1))
print(ob1.isSymmetric(tree2))
입력
tree1 = make_tree([1, 2, 2, 3, 4, 4, 3])
tree2 = make_tree([1, 2, 2, 3, 4, None, 3])
출력
True
False
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이(h)에 비례하며, 최악의 경우(편향된 트리) O(n)까지 증가할 수 있습니다.