Subtree of Another Tree

문제 링크

• https://leetcode.com/problems/subtree-of-another-tree/

문제 설명

주어진 두 개의 이진 트리 root와 subRoot가 있을 때, root 트리의 어떤 서브트리가 subRoot와 동일한 구조와 값을 가지고 있는지를 확인하는 함수를 작성하세요. 서브트리는 트리의 어떤 노드와 그 노드의 모든 자손으로 구성된 트리를 의미합니다. 주어진 트리 root가 자신을 서브트리로 간주할 수도 있습니다.

예제

• 예제 1
  • 입력: root = [3,4,5,1,2], subRoot = [4,1,2]
  • 출력: true
  • 설명: root 트리에서 4를 루트로 하는 서브트리는 subRoot와 동일한 구조와 값을 가집니다.
• 예제 2
  • 입력: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
  • 출력: false
  • 설명: root의 어떤 서브트리도 subRoot와 동일하지 않으므로 false를 반환합니다.

풀이 전략

이 문제를 해결하기 위한 일반적인 접근 방법은 다음과 같습니다:

1. 서브트리 탐색:
   • root 트리의 각 노드를 탐색하며, 각 노드가 subRoot의 루트가 될 수 있는지 확인합니다.
2. 트리 비교:
   • 어떤 노드가 subRoot의 루트와 같다고 가정할 때, 그 서브트리와 subRoot가 동일한지 확인하는 함수를 호출합니다.
3. 재귀적 접근:
   • 두 트리의 노드가 동일한지 확인하기 위해 재귀적으로 비교하는 방법을 사용할 수 있습니다.

코드 분석

코드 구현

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True  # 빈 서브트리는 항상 존재

        if not root:
            return False  # root가 None인데 subRoot가 있는 경우

        if self.isSameTree(root, subRoot):
            return True  # 현재 root 노드가 subRoot와 같은 경우

        # 왼쪽과 오른쪽 서브트리에서 탐색
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True  # 두 노드가 모두 None인 경우
        if not p or not q:
            return False  # 하나만 None인 경우

        if p.val != q.val:
            return False  # 두 노드의 값이 다를 경우

        # 왼쪽 서브트리와 오른쪽 서브트리 비교
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

• isSubtree 함수:
  • subRoot가 비어있으면 항상 True를 반환합니다.
  • root가 비어있으면 False를 반환합니다.
  • 현재 root 노드와 subRoot가 동일한지를 isSameTree 함수를 통해 확인합니다.
  • 동일하지 않은 경우, 왼쪽과 오른쪽 서브트리에서 재귀적으로 isSubtree를 호출하여 탐색합니다.
• isSameTree 함수:
  • 두 노드가 모두 None이면 True를 반환합니다.
  • 한 쪽만 None인 경우 False를 반환합니다.
  • 두 노드의 값이 다르면 False를 반환합니다.
  • 두 서브트리를 재귀적으로 비교합니다.
• 시간 복잡도: (O(m \cdot n)) - root의 모든 노드에 대해 subRoot와 비교하는 데 걸리는 시간, 여기서 (m)은 root의 노드 수, (n)은 subRoot의 노드 수입니다.
• 공간 복잡도: (O(h)) - 재귀 호출 스택의 깊이는 트리의 높이에 비례합니다. 최악의 경우 (h)는 (O(m))일 수 있습니다.

요약

• 주어진 두 이진 트리의 서브트리 비교 문제로, root의 각 노드에 대해 subRoot와의 동일성을 확인하는 방식으로 접근합니다.
• 재귀적으로 트리를 비교하는 방법을 사용하며, 시간 복잡도는 (O(m \cdot n))입니다.