LeetCode

LeetCode 572 Subtree of Another Tree 풀이: 이진 트리 DFS와 구조 비교

2026년 9월 8일

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

0. 문제 링크와 출처

문제: 572. Subtree of Another Tree
출처: LeetCode
자체 판단 난이도: Level 3

큰 이진 트리의 각 노드를 부분 트리의 시작점으로 삼아 두 트리의 구조와 값을 비교하는 문제다. 이진 트리 순회와 두 트리의 동일성 비교를 조합해야 하므로 Level 3으로 판단했다.

1. 문제 요약

두 이진 트리의 루트 root와 subRoot가 주어진다. subRoot가 root 안에 있는 어떤 노드를 루트로 하는 부분 트리와 구조 및 노드 값이 모두 같으면 true, 그렇지 않으면 false를 반환한다.

부분 트리는 하나의 노드와 그 노드의 모든 자손으로 이루어진다. 단순히 subRoot의 값들이 root 안에 존재하는지만 확인해서는 안 되고, 각 위치의 왼쪽·오른쪽 자식 구조와 값까지 같아야 한다.

문제의 제한에서 root의 노드 수는 최대 2,000개이고 subRoot의 노드 수는 최대 1,000개다. 모든 후보 위치에서 두 트리를 비교하는 방식도 이 제한 안에서 처리할 수 있다.

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

핵심 관찰

subRoot가 root의 부분 트리인지 확인하는 과정은 두 단계로 나눌 수 있다.

root의 모든 노드를 DFS로 방문하며 부분 트리의 후보를 찾는다.
각 후보 노드를 subRoot의 루트와 비교해 두 트리가 완전히 같은지 확인한다.

두 노드가 같은 값을 가지더라도 한쪽에만 자식이 있거나 자식 값이 다르면 같은 트리가 아니다. is_same_tree 함수는 현재 노드의 값뿐 아니라 왼쪽과 오른쪽 서브트리의 비교 결과까지 모두 확인해야 한다.

후보 노드와 동일성 비교

is_subtree(root, subRoot)에서는 다음 순서로 판단한다.

root가 None이면 더 이상 후보가 없으므로 False다.
현재 root를 subRoot와 비교해 같으면 True다.
같지 않으면 root.left와 root.right를 각각 새로운 후보로 탐색한다.

동일성 비교에서는 두 노드가 모두 None이면 같은 구조의 끝으로 보고 True를 반환한다. 한쪽만 None이거나 값이 다르면 False이며, 그 외에는 양쪽 자식을 재귀적으로 비교한다.

3. 문제 해결 코드 (Python)

class Solution:
    def isSubtree(self, root: 'TreeNode | None', subRoot: 'TreeNode | None') -> bool:
        def is_same_tree(first, second):
            if first is None and second is None:
                return True
            if first is None or second is None:
                return False
            if first.val != second.val:
                return False

            return (is_same_tree(first.left, second.left)
                    and is_same_tree(first.right, second.right))

        if root is None:
            return False
        if is_same_tree(root, subRoot):
            return True

        return (self.isSubtree(root.left, subRoot)
                or self.isSubtree(root.right, subRoot))

root의 노드 수를 m, subRoot의 노드 수를 n이라고 하면, 최악의 경우 root의 각 노드에서 subRoot 전체를 비교하므로 시간 복잡도는 O(m × n)이다.

추가 자료구조는 사용하지 않지만 두 DFS의 재귀 호출 스택이 필요하다. 트리 높이를 각각 h_root, h_subRoot라고 하면 공간 복잡도는 O(h_root + h_subRoot)이며, 편향 트리에서는 최악의 경우 O(m + n)이다.

4. 오답 접근과 반례

노드 값만 순회해 비교하기

값만 전위 순회해 리스트로 만든 뒤 포함 여부를 검사하면 트리의 구조를 보존하지 못한다. 다음 두 트리는 값 순서만 보면 모두 [1, 2]처럼 보일 수 있다.

첫 번째:       1          두 번째:       1
              /                        \
             2                          2

하지만 첫 번째 트리는 왼쪽 자식이고 두 번째 트리는 오른쪽 자식이므로 서로 다른 구조다. 직렬화 방식으로 해결하려면 None을 나타내는 표식도 반드시 포함해야 하며, 이 글에서는 더 직접적인 두 트리 재귀 비교를 사용한다.

값이 같은 후보에서 즉시 성공 처리하기

현재 노드의 값이 subRoot.val과 같다고 해서 부분 트리가 완성된 것은 아니다. root의 후보에 자식 0이 더 있지만 subRoot에는 해당 자식이 없다면 두 트리는 다르다. 후보 노드의 양쪽 자식까지 모두 비교해야 한다.

복사해 실행할 테스트

로컬 실행 시 아래 TreeNode 보조 클래스를 풀이 코드보다 먼저 두고 assert를 뒤에 붙인다. 포함되는 서브트리와 값이 다른 후보를 확인한다.

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

solver = Solution()
root = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(5))
sub = TreeNode(4, TreeNode(1), TreeNode(2))
assert solver.isSubtree(root, sub) is True
assert solver.isSubtree(root, TreeNode(4, TreeNode(1), TreeNode(3))) is False

5. 공식 예제와 추가 검증

LeetCode 공식 예제 2개와 트리 구조 비교에 필요한 추가 사례를 Python 3.11에서 테스트용 TreeNode 클래스로 재현해 확인했다.

예제	기대 출력	확인 결과
`root=[3,4,5,1,2], subRoot=[4,1,2]`	`True`	통과
`root=[3,4,5,1,2,null,null,null,null,0], subRoot=[4,1,2]`	`False`	통과

추가 검증 1: root 전체가 subRoot인 경우

입력: root = [1,2,3], subRoot = [1,2,3]
기대 출력: True
확인 결과: 통과
검증 목적: 큰 트리 자체도 자신의 부분 트리로 인정하는지 확인

추가 검증 2: 같은 값이지만 자식 방향이 다른 경우

입력: root = [1,2], subRoot = [1,null,2]
기대 출력: False
확인 결과: 통과
검증 목적: 노드 값뿐 아니라 왼쪽·오른쪽 구조를 비교하는지 확인

추가 검증 3: 단일 노드 부분 트리

입력: root = [3,4,5], subRoot = [5]
기대 출력: True
확인 결과: 통과
검증 목적: root의 리프 노드도 후보가 되는지 확인

추가 검증 4: 값이 같은 후보지만 구조가 더 큰 경우

입력: root = [1,2,3,4], subRoot = [2]
기대 출력: False
확인 결과: 통과
검증 목적: 값이 같은 것만으로 부분 트리라고 판단하지 않는지 확인

6. 다른 풀이 방식 검색 및 비교

Subtree of Another Tree 공식 문제는 subRoot가 root의 어떤 부분 트리와 구조 및 값을 모두 공유하는지 묻는다.
AlgoMonster의 설명은 root를 DFS로 순회하면서 각 후보에 대해 두 트리가 같은지 확인하는 접근을 설명한다.

트리를 전위 순회 문자열로 직렬화한 뒤 문자열 검색 문제로 바꾸는 방법도 있다. 이 경우 서로 다른 구조가 같은 문자열로 합쳐지지 않도록 None 표식과 구분자를 넣어야 한다. 직렬화와 문자열 검색을 사용하면 최적화 여지가 있지만, 이 글에서는 문제의 구조를 그대로 표현하고 구현이 단순한 DFS와 재귀 비교 방식을 선택했다.

마무리

Subtree of Another Tree는 큰 트리에서 후보 노드를 찾는 DFS와 두 트리의 구조를 비교하는 재귀를 결합하는 문제다. 현재 노드의 값만 비교하지 않고 None 여부와 양쪽 자식까지 함께 확인해야 정확한 부분 트리 판별이 가능하다.