LeetCode 100 Same Tree 풀이: 트리 동시 순회

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 100. Same Tree
• 출처: LeetCode
• 자체 판단 난이도: Level 3

두 이진 트리의 루트를 받아 같은 위치의 구조와 값이 모두 일치하는 문제다. 이진 트리 구조를 이해하고 두 트리를 동시에 재귀 순회해야 하므로 Level 3으로 판단했다.

1. 문제 요약

두 이진 트리 p와 q가 다음 조건을 모두 만족하면 같은 트리다.

• 구조가 동일하다.
• 같은 위치에 있는 두 노드의 값이 같다.

두 트리가 모두 비어 있으면 같고, 한쪽만 비어 있으면 다르다. 루트부터 시작해 왼쪽 서브트리와 오른쪽 서브트리를 대응시켜 재귀적으로 비교한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

트리 구조와 동시 순회

두 트리가 같으려면 현재 노드와 양쪽 서브트리가 모두 일치해야 한다. 다음 세 조건을 순서대로 확인하면 된다.

1. 두 노드가 모두 None이면 같다.
2. 한쪽만 None이거나 값이 다르면 다르다.
3. 값이 같으면 왼쪽, 오른쪽 서브트리를 같은 방식으로 비교한다.

현재 노드의 값이 일치해도 서브트리 구조가 다르면 같지 않으므로, and로 양쪽 서브트리 비교 결과를 모두 요구한다.

왜 동시에 순회하는가

한 트리의 노드만 따라가면 두 번째 트리의 같은 위치에 어떤 노드가 있는지 알 수 없다. 두 트리의 루트에서 출발해 같은 방향으로 함께 내려가야 구조와 값의 일치를 같은 좌표에서 판단할 수 있다.

paired-node 불변식

재귀 호출의 인자는 항상 두 트리에서 같은 경로를 따라 내려온 한 쌍의 노드다. 호출이 True를 반환한다는 것은 그 두 노드의 값과 왼쪽·오른쪽 자식 쌍이 모두 일치한다는 뜻이다. 한쪽만 None인 순간에는 대응 위치의 구조가 달라진 것이므로 더 내려갈 필요가 없고, 두 쪽이 모두 None인 경우에만 해당 서브트리의 비교가 끝난 것으로 처리한다.

3. 문제 해결 코드 (Python)

class Solution:
    def isSameTree(self, p: 'TreeNode', q: 'TreeNode') -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False

        return (self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))

두 트리를 같은 위치끼리 한 번씩 방문하므로 노드 수를 각각 m, n이라고 하면 시간 복잡도는 O(min(m, n))이다. 값이 달라지거나 구조가 달라지면 즉시 반환한다. 공간 복잡도는 재귀 호출 스택에 비례해 O(H)이며, 편향 트리에서는 O(n)이 된다.

4. 오답 접근과 반례

한 트리만 전위 순회해 노드 값을 리스트로 만들고 두 리스트가 같은지 비교하면 서로 다른 구조의 트리를 같다고 판단할 수 있다. [1, 2]와 [1, None, 2]는 둘 다 같은 값 목록처럼 보일 수 있지만, 전자는 왼쪽 자식이 2이고 후자는 오른쪽 자식이 2인 다른 구조이므로 같지 않다.

값만 비교하지 말고 자식의 존재 여부까지 구조로 함께 비교해야 한다.

복사해 실행할 테스트

로컬 실행 시 아래 TreeNode 보조 클래스를 풀이 코드보다 먼저 두고 assert를 뒤에 붙인다. 구조·값 일치와 값 불일치 사례를 비교한다.

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

solver = Solution()
assert solver.isSameTree(TreeNode(1, TreeNode(2), TreeNode(3)), TreeNode(1, TreeNode(2), TreeNode(3))) is True
assert solver.isSameTree(TreeNode(1, TreeNode(2)), TreeNode(1, None, TreeNode(2))) is False

5. 공식 예제와 추가 검증

LeetCode 공식 예제 3개를 Python 3.12.4에서 테스트용 TreeNode 클래스로 재현해 검증했다.

추가 검증 1: 두 트리가 모두 빈 경우

입력: p = None, q = None
기대 출력: true
확인 결과: 통과
검증 목적: 빈 트리끼리 같다고 판단하는지 확인

추가 검증 2: 한쪽만 비어 있는 경우

입력: p = [1], q = None
기대 출력: false
확인 결과: 통과
검증 목적: 한쪽만 비어 있을 때 다르다고 판단하는지 확인

추가 검증 3: 같은 값의 단일 노드

입력: p = [5], q = [5]
기대 출력: true
확인 결과: 통과
검증 목적: 값과 구조가 모두 같은 최소 트리 확인

추가 검증 4: 값이 다른 단일 노드

입력: p = [1], q = [2]
기대 출력: false
확인 결과: 통과
검증 목적: 구조가 같아도 값이 다르면 다른 트리인지 확인

6. 참고 풀이 비교

• Same Tree 공식 문제는 구조와 노드 값이 모두 같을 때 두 트리를 동일하다고 정의한다.
• AlgoMonster의 설명은 두 노드가 모두 None인지, 값이 같은지, 양쪽 서브트리가 같은지를 재귀로 확인하는 접근을 설명한다.

재귀 DFS는 트리의 대응 구조를 표현하기에 자연스럽다. 두 트리를 함께 순회한다는 점에서 큐를 사용하는 BFS로도 풀 수 있지만, 이 글에서는 점화 관계를 그대로 옮긴 재귀 방식을 선택했다.

마무리

Same Tree는 두 트리를 같은 좌표의 노드끼리 비교하는 동시 순회 문제다. 두 노드가 모두 없는 경우를 먼저, 한쪽만 없는 경우와 값이 다른 경우를 구분한 뒤 양쪽 서브트리를 재귀적으로 확인하면 구조와 값의 일치를 모두 판단할 수 있다.