← 전체 회차
A-051● Day 512026.06.26easyleetcode #572neetcode150

다른 트리의 부분트리

#tree#depth-first-search#string-matching#binary-tree#hash-function
↗ leetcode #572 · subtree-of-another-tree
01

문제

· problem
P.051

다른 트리의 부분트리

↗ leetcode #572

두 개의 이진 트리의 루트 root와 subRoot가 주어질 때, root의 부분트리 중에 subRoot와 같은 구조와 노드 값을 가진 트리가 있으면 true를, 그렇지 않으면 false를 반환합니다. 이진 트리 tree의 부분트리는 tree의 한 노드와 그 노드의 모든 자손으로 이루어진 트리입니다. tree 자신도 tree의 부분트리로 간주될 수 있습니다.

제약
  • · 1 ≤ nodes in root ≤ 2000
  • · 1 ≤ nodes in subRoot ≤ 1000
  • · -10^4 ≤ node values ≤ 10^4
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,4,5,1,2]
[4,1,2]
true
example 2input → output
[3,4,5,1,2,null,null,null,null,0]
[4,1,2]
false
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    subRoot가 null이면 true를 반환해야 할까?
  • ☐
    부분트리가 메인 트리의 루트에서 시작해야 할까?
  • ☐
    root = [4,1,2]이고 subRoot = [4,1,2]이면, subRoot는 root의 부분트리인가?
  • ☐
    값이 1과 2를 포함하면 [1,2]는 [4,1,2]의 부분트리인가?
  • ☐
    root.val == subRoot.val 확인만 충분한가?
  • ☐
    root에서 subRoot의 값이 어떤 순서로든 나타나면 찾을 수 있을까?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 빈 subRoot 확인
○
if not subRoot:
○
if subRoot: return True
○
if not subRoot: pass
step 2· 빈 root 확인
○
if not root:
○
if not root: return True
○
if root and not subRoot: return False
step 3· 현재 노드의 부분트리 비교
○
if self.isSameTree(root, subRoot):
○
if root.val == subRoot.val:
○
if self.isSubtree(root, subRoot):
step 4· 왼쪽과 오른쪽 부분트리 재귀 탐색
○
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
○
return self.isSubtree(root.left, subRoot) and self.isSubtree(root.right, subRoot)
○
return self.isSubtree(root, subRoot.left) or self.isSubtree(root, subRoot.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, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
9
        if not subRoot:
10
            return True
11
        if not root:
12
            return False
13
14
        if self.isSameTree(root, subRoot):
15
            return True
16
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
17
18
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
19
        if not p and not q:
20
            return True
21
        if p and q and p.val == q.val:
22
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
23
        else:
24
            return False
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,4,5,1,2]
[4,1,2]
→
true
case 2
[3,4,5,1,2,null,null,null,null,0]
[4,1,2]
→
false
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.