문제 소개
두 개의 이진 트리(binary tree)가 주어졌을 때, 각 트리를 왼쪽에서 오른쪽 순서로 읽었을 때의 잎(leaf) 노드 시퀀스가 서로 동일한지 판별하는 프로그램을 작성해 보겠습니다. 여기서 잎 노드란 왼쪽과 오른쪽 자식을 모두 가지지 않는 노드를 의미합니다.
예를 들어 아래와 같은 두 트리가 입력으로 주어진다고 가정해 봅시다.
두 트리 모두 왼쪽에서 오른쪽으로 잎 노드를 읽으면 [2, 6]이 되므로, 결과는 True입니다.
풀이 접근 방법
이 문제는 중위 순회(inorder traversal)를 응용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 각 트리를 순회하면서 잎 노드의 값만 순서대로 수집한 뒤, 두 결과 리스트를 비교하는 것입니다. 구체적인 단계는 다음과 같습니다.
- 잎 노드 값을 담을 빈 리스트
c를 준비합니다. inorder()함수를 정의합니다. 이 함수는 루트 노드(root)와 리스트c를 매개변수로 받습니다.c가 None이면 새 리스트를 생성합니다.root가 None이 아니라면 다음 작업을 수행합니다.- 루트의 왼쪽 서브트리에 대해
inorder()를 재귀 호출합니다. - 루트의 왼쪽과 오른쪽 자식이 모두 없다면, 즉 현재 노드가 잎 노드라면 그 값을
c의 끝에 추가합니다. - 루트의 오른쪽 서브트리에 대해
inorder()를 재귀 호출합니다.
- 루트의 왼쪽 서브트리에 대해
- 순회가 끝나면
c를 반환합니다.
메인 메서드에서는 두 트리의 루트 각각에 대해 inorder()를 호출한 결과가 완전히 같으면 True, 하나라도 다르면 False를 반환하면 됩니다.
구현 예제 코드
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def inorder(self, root, c=None):
if c is None:
c = []
if root:
self.inorder(root.left, c)
# 왼쪽과 오른쪽 자식이 모두 없으면 잎 노드
if not root.left and not root.right:
c.append(root.val)
self.inorder(root.right, c)
return c
def solve(self, root0, root1):
return self.inorder(root0) == self.inorder(root1)
ob = Solution()
root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6)
root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
print(ob.solve(root1, root2))
입력
root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6)
root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
출력
True
동작 원리 살펴보기
첫 번째 트리는 루트 1의 오른쪽에 노드 3이 있고, 3의 자식으로 2와 6이 연결되어 있습니다. 따라서 잎 노드는 2와 6이며, 중위 순회 순서대로 수집하면 [2, 6]이 됩니다.
두 번째 트리는 루트 1의 왼쪽에 노드 3(자식 2), 오른쪽에 노드 6이 있는 구조입니다. 잎 노드 역시 2와 6이므로 수집 결과는 [2, 6]으로 동일합니다. 두 리스트가 같기 때문에 최종 결과로 True가 출력됩니다.
시간 및 공간 복잡도
- 시간 복잡도: O(N₁ + N₂) — 각 트리의 모든 노드를 한 번씩 방문합니다. 여기서 N₁, N₂는 각 트리의 노드 수입니다.
- 공간 복잡도: O(H₁ + H₂) — 재귀 호출 스택이 트리의 높이만큼 사용되며, 잎 노드 값을 저장하는 리스트도 추가로 필요합니다.
마무리
이처럼 중위 순회를 활용하면 두 이진 트리의 잎 노드 시퀀스를 손쉽게 비교할 수 있습니다. 트리의 전체 구조가 달라도 잎 노드의 값과 순서만 일치하면 True를 반환한다는 점이 이 문제의 핵심입니다. 실무에서는 트리 비교, 데이터 검증 등 다양한 상황에서 응용할 수 있는 유용한 기법이니 꼭 기억해 두세요.