파이썬으로 두 이진 트리의 리프 순회가 동일한지 확인하는 방법

문제 개요

두 개의 이진 트리(binary tree)가 주어졌을 때, 두 트리의 리프 순회(leaf traversal)가 서로 동일한지 확인하는 문제입니다. 여기서 리프 순회란 트리를 왼쪽에서 오른쪽으로 훑으면서 만나는 리프(자식이 없는 노드) 값들의 순서를 의미합니다.

예를 들어 아래와 같은 두 트리가 있다고 가정해 보겠습니다.

두 트리의 전체 구조는 서로 다르지만, 왼쪽에서 오른쪽으로 읽었을 때 리프 값의 순서가 모두 [5, 7, 8]로 동일하므로 결과는 True가 됩니다.

접근 방법: 스택을 이용한 동시 순회

재귀 호출 대신 스택(stack)을 활용하면 두 트리를 동시에 순회하면서 리프 노드를 하나씩 짝지어 비교할 수 있습니다. 알고리즘의 진행 순서는 다음과 같습니다.

두 개의 빈 리스트(스택) s1, s2를 준비하고, 각각 루트 노드 r1과 r2를 삽입합니다.
s1 또는 s2 중 하나라도 요소가 남아 있는 동안 다음을 반복합니다.
- 둘 중 하나라도 스택이 비어 있으면 False를 반환합니다.
- s1에서 노드를 꺼낸 뒤, 리프 노드가 나올 때까지 오른쪽 자식과 왼쪽 자식을 차례로 스택에 push하며 내려갑니다. 왼쪽 자식을 나중에 push하므로 왼쪽 방향 탐색이 우선됩니다.
- s2에 대해서도 동일한 과정을 수행합니다.
- 각 트리에서 꺼낸 두 노드를 비교합니다. 한쪽만 null이거나 두 노드의 값이 서로 다르면 False를 반환합니다.
반복이 정상적으로 끝나면 모든 리프가 일치한다는 뜻이므로 True를 반환합니다.

구현 예제

아래는 위 알고리즘을 파이썬으로 구현한 코드입니다.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = self.right = None

    def is_leaf(self):
        return self.left == None and self.right == None

def solve(r1, r2):
    s1 = []
    s2 = []
    s1.append(r1)
    s2.append(r2)

    while len(s1) != 0 or len(s2) != 0:
        if len(s1) == 0 or len(s2) == 0:
            return False

        r1_node = s1.pop(-1)
        while r1_node != None and not r1_node.is_leaf():
            if r1_node.right != None:
                s1.append(r1_node.right)
            if r1_node.left != None:
                s1.append(r1_node.left)
            r1_node = s1.pop(-1)

        r2_node = s2.pop(-1)
        while r2_node != None and not r2_node.is_leaf():
            if r2_node.right != None:
                s2.append(r2_node.right)
            if r2_node.left != None:
                s2.append(r2_node.left)
            r2_node = s2.pop(-1)

        if r1_node == None and r2_node != None:
            return False
        if r1_node != None and r2_node == None:
            return False
        if r1_node != None and r2_node != None:
            if r1_node.val != r2_node.val:
                return False

    return True

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)

root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

print(solve(root1, root2))

입력

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)

root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

출력

True

복잡도 분석

시간 복잡도: 두 트리의 모든 노드를 최대 한 번씩 방문하므로 O(n + m)입니다. (n, m은 각 트리의 노드 수)
공간 복잡도: 스택에는 한 경로의 노드들만 저장되므로 트리 높이 h에 비례하는 O(h)입니다.

이처럼 스택 기반 순회를 사용하면 트리의 전체 구조가 달라도 리프 노드의 왼쪽→오른쪽 순서만 일치하면 된다는 조건을 효율적으로 검증할 수 있습니다.