[DSA][Trees] 06. Subtree of Another Tree

LeetCode 572

 

06. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants.
The tree tree could also be considered as a subtree of itself.

 

 

[질문하기]

- 노드의 값에 중복이 있을 수 있나요?

- subRoot가 null인 경우, 항상 true를 반환하나요?

 

[아이디어]

- DFS를 사용하여 재귀적으로 same 여부를 판단하자.

- 트리를 preorder로 순회하여 문자열로 만들자.

 

 

[풀이 1] Depth First Search

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        elif not root:
            return False
        
        if self.isSameTree(root, subRoot):
            return True
        
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

저번 포스팅에서 두 트리가 같은지 판별하는 Same Tree 문제를 다뤘다. 2025.07.14 - [자료구조와 알고리즘] - [DSA][Trees] 05. Same Tree

이번 문제는 이와 유사하지만, root 트리 내에 subRoot와 동일한 구조와 값을 가진 서브트리가 존재하는지를 찾는 문제다.

핵심 아이디어는 root 트리의 각 노드를 기준으로 삼아, 그 노드를 루트로 하는 서브트리가 subRoot와 같은지 확인하는 것이다. 이를 위해 root의 왼쪽, 오른쪽 자식 노드를 재귀적으로 탐색하면서, sameTree(root, subRoot) 함수를 호출해 두 트리가 같은지 검사한다.

 

⏱️ 시간복잡도

root 트리의 모든 노드(N개)에 대해 subRoot 트리(M개 노드)와 같은지 비교하므로 최악의 경우 O(N × M) 만큼의 연산이 발생한다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 root 트리의 최대 높이 H와 subRoot 트리의 최대 높이 subH가 더해진 만큼의 깊이 O(H + subH)에 비례한다. 따라서 공간 복잡도는 최악의 경우 O(N + M) (Skew 트리)이고, 평균적으로는 O(logN + logM) (균형 잡힌 트리)이다.

 

 

[풀이 2] Serialization And Pattern Matching

class Solution:
    def isSubtree(self, root, subRoot):
        def treeToStr(node):
            if not node:
                return "#"
            return f"{node.val},{treeToStr(node.left)},{treeToStr(node.right)}"

        def subTreeStrs(node):
            if not node:
                return "#"
            key = f"{node.val},{subTreeStrs(node.left)},{subTreeStrs(node.right)}"
            allSubTrees.add(key)
            return key

        allSubTrees = set()
        subTreeStrs(root)
        subRootStr = treeToStr(subRoot)
        return subRootStr in allSubTrees

첫 번째 풀이에서는 root 트리의 모든 노드에 대해 subRoot와 비교하기 때문에 시간 복잡도가 O(N × M)으로 커졌다.

하지만 root 트리가 가질 수 있는 모든 서브트리를 Preorder 방식으로 직렬화하여 문자열로 만든 뒤, 이를 set에 저장해 두고, subRoot도 같은 방식으로 직렬화하여 해당 문자열이 set 안에 존재하는지만 확인한다면 비교 비용을 크게 줄일 수 있다.

문자열 직렬화는 Preorder 순회로 진행하며, 자식 노드가 없을 경우에는 # 기호를 붙여 구분한다.

ex) root : [3,4,5,1,2] → allSubTrees: {'2,#,#', '5,#,#', '4,1,#,#,2,#,#', '3,4,1,#,#,2,#,#,5,#,#', '1,#,#'}

 

⏱️ 시간복잡도

각 노드를 기준으로 하는 서브트리 직렬화를 한 번만 계산하여 저장해 두므로, 전체 계산은 트리 크기 N에 비례하는 O(N) 시간에 가능하다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 root 트리의 최대 높이와 subRoot 트리의 최대 높이 O(H + subH)에 비례하고, 따라서 공간 복잡도는 최악의 경우 O(N + M) (Skew 트리)이고, 평균적으로는 O(logN + logM) (균형 잡힌 트리)이다.