← 전체 회차
A-050● Day 502026.06.25easyleetcode #100neetcode150

같은 트리

#tree#depth-first-search#breadth-first-search#binary-tree
↗ leetcode #100 · same-tree
01

문제

· problem
P.050

같은 트리

↗ leetcode #100

두 이진 트리의 루트 p와 q가 주어질 때, 두 트리가 동일한지 확인하는 함수를 작성하세요. 두 이진 트리가 같다고 간주되려면 구조적으로 동일하고 노드의 값이 모두 같아야 합니다.

제약
  • · The number of nodes in both trees is in the range [0, 100]
  • · -10⁴ ≤ Node.val ≤ 10⁴
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,2,3]
[1,2,3]
true
example 2input → output
[1,2]
[1,null,2]
false
example 3input → output
[1,2,1]
[1,1,2]
false
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    두 트리가 모두 비어있으면 같다고 봐야 하나요?
  • ☐
    한 트리는 null이고 다른 트리는 노드가 있으면 어떻게 되나요?
  • ☐
    노드의 값이 같아도 좌우 자식의 위치가 다르면 같은 트리인가요?
  • ☐
    반복적인 방법(iterative)으로 해결할 수 있나요?
  • ☐
    두 트리를 문자열로 직렬화하고 비교할 수 있나요?
  • ☐
    중순 순회(inorder traversal) 결과만 비교하면 충분한가요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 기저 사례: 두 노드 모두 null
○
if not p and not q:
○
if not p or not q:
○
if p is None and q is None:
step 2· 기저 사례 반환값│ 중첩
○
return True
○
return False
○
continue
step 3· 재귀 조건: 두 노드 모두 존재하고 값이 같음
○
if p and q and p.val == q.val:
○
if p or q and p.val == q.val:
○
if p and q and p.val != q.val:
○
if p and q:
step 4· 재귀 호출: 좌우 부분 트리 비교│ 중첩
○
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
○
return self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)
○
return self.isSameTree(p.left, q.left) or self.isSameTree(p.right, q.right)
○
return self.isSameTree(p, q)
step 5· 불일치 경우: false 반환
○
else:
○
else: return True
○
else: return self.isSameTree(p.right, q.right)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, x):
4
#         self.val = x
5
#         self.left = None
6
#         self.right = None
7
8
9
class Solution:
10
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
11
        if not p and not q:
12
            return True
13
        if p and q and p.val == q.val:
14
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
15
        else:
16
            return False
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,2,3]
[1,2,3]
→
true
case 2
[1,2]
[1,null,2]
→
false
case 3
[1,2,1]
[1,1,2]
→
false
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.