Same Tree

문제 링크

• https://leetcode.com/problems/same-tree/

문제 설명

두 개의 이진 트리 p와 q의 루트가 주어질 때, 이 두 트리가 동일한 구조와 값을 가지는지를 확인하는 함수를 작성하세요. 두 이진 트리는 다음과 같은 조건을 만족할 때 동일하다고 간주됩니다:

1. 두 트리의 구조가 동일해야 합니다. (즉, 각 노드가 자식을 가지고 있는 방식이 같아야 함)
2. 각 노드의 값이 동일해야 합니다.

예제

• 예제 1
  • 입력: p = [1,2,3], q = [1,2,3]
  • 출력: true
  • 설명: 두 트리는 동일한 구조와 값을 가집니다.
• 예제 2
  • 입력: p = [1,2], q = [1,null,2]
  • 출력: false
  • 설명: p 트리는 두 자식을 가진 노드가 있지만, q 트리는 하나의 자식만 가집니다.
• 예제 3
  • 입력: p = [1,2,1], q = [1,1,2]
  • 출력: false
  • 설명: 두 트리의 구조는 동일하지만, 노드의 값이 다릅니다.

풀이 전략

이 문제를 해결하기 위해서는 재귀적 방법을 사용할 수 있습니다. 각 노드를 순회하면서 두 가지 조건을 확인해야 합니다.

1. 노드 값 비교: 두 노드의 값이 같아야 합니다.
2. 서브트리 비교: 왼쪽 서브트리와 오른쪽 서브트리를 각각 비교합니다.

이 조건들을 재귀적으로 적용하여 두 트리의 모든 노드를 검사하면 됩니다.

코드 분석

재귀적 접근

class Solution:
    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)

• 동작 원리:
  • 첫 번째 조건으로 두 노드가 모두 None이면 두 트리는 동일하다고 판단하고 True를 반환합니다.
  • 두 번째 조건으로 한 쪽 노드가 None이고 다른 쪽 노드가 None이 아닌 경우, 두 트리는 다르므로 False를 반환합니다.
  • 세 번째 조건에서 두 노드의 값이 다르면, 두 트리는 다르므로 False를 반환합니다.
  • 마지막으로, 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 비교하여 두 트리가 동일한지 여부를 확인합니다.
• 시간 복잡도: (O(n)) - 모든 노드를 한 번씩 방문합니다.
• 공간 복잡도: (O(h)) - 재귀 호출 스택의 깊이는 트리의 높이에 비례하며, 최악의 경우 (h)는 (n)과 같을 수 있습니다 (편향 트리).

요약

• 주어진 두 이진 트리의 구조와 값을 비교하는 문제로, 재귀적 접근 방법을 통해 쉽게 해결할 수 있습니다.
• 각 노드의 값과 서브트리를 재귀적으로 비교하여 두 트리가 동일한지 판단합니다.
• 시간 복잡도는 (O(n))이며, 공간 복잡도는 트리의 높이에 따라 (O(h))입니다.