[DSA][Trees] 05. Same Tree

LeetCode 100

 

05. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

 

[질문하기]

- 구조적으로 같다는 것은 자식 노드의 null 위치까지도 동일해야 한다는 의미인가요?

 

[아이디어]

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

 

 

[풀이 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

두 노드를 동시에 탐색하면서, 값이 같은지를 확인한다.
이때 두 노드가 모두 존재하고 값도 같다면, 각각 왼쪽 서브트리와 오른쪽 서브트리도 같은지를 재귀적으로 판단하면 된다.

 

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 O(h)에 비례하고 따라서 공간 복잡도는 최악의 경우 O(N) (Skew 트리)이고, 평균적으로는 O(log N) (균형 잡힌 트리)이다.