Oct 26, 2025

TIL

[Algorithm] 이진 트리 isSubtree 판별 (LeetCode 572)

1. 문제 정의

root 트리에 subRoot와 완벽히 동일한 (구조와 값 모두) 서브트리가 존재하는지 확인하는 문제.

2. 핵심 로직: 2-Step 재귀

이 문제는 두 가지 다른 재귀 함수가 필요하다.

A. isSameTree (트리 동일성 검사)

두 트리가 루트부터 시작해서 완전히 똑같이 생겼는지 확인하는 헬퍼 함수.

• Base Case 1: 두 노드 p, q가 모두 null이면 -> true (구조 일치)
• Base Case 2: p나 q 둘 중 하나만 null이거나, p.val != q.val이면 -> false (불일치)
• Recursive Step: isSameTree(p.left, q.left) AND isSameTree(p.right, q.right)
  • (왼쪽 자식 그리고 오른쪽 자식 모두 동일해야 함)

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null || p.val != q.val) return false;
    
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

B. isSubtree (서브트리 탐색)

root 트리의 모든 노드를 순회하며 “이 노드에서 시작하는 트리가 subRoot와 동일한가?”를 묻는 함수.

• Base Case 1: subRoot가 null이면 -> true (빈 트리는 항상 서브트리)
• Base Case 2: root가 null이면 (subRoot는 null이 아님) -> false (찾을 곳이 없음)
• Recursive Step: 3가지 조건 중 하나라도 만족하면 true (OR 연산)
  1. isSameTree(root, subRoot) : 현재 root에서 시작하는 트리가 subRoot와 동일한가?
  2. isSubtree(root.left, subRoot) : 또는 subRoot가 왼쪽 서브트리 안에 있는가?
  3. isSubtree(root.right, subRoot) : 또는 subRoot가 오른쪽 서브트리 안에 있는가?

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) return true;
    if (root == null) return false;
    
    return isSameTree(root, subRoot) || 
           isSubtree(root.left, subRoot) || 
           isSubtree(root.right, subRoot);
}

---

3. 내가 겪은 함정 (The “Aha!” Moment) 💡

나는 처음에 isSubtree를 이렇게 잘못 작성했었다.

// ❌ 잘못된 코드 (Premature Return)
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) return true;
    if (root == null) return false;

    if (root.val == subRoot.val) {
        // ★★★ 여기가 문제! ★★★
        // isSameTree가 false를 반환하면,
        // isSubtree(root.left, ...)를 탐색할 기회도 없이
        // 함수 전체가 즉시 false를 반환하고 끝나버림!
        return isSameTree(root, subRoot); 
    }

    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

💣 이 코드가 실패한 결정적 케이스

• root = [1, 1]
• subRoot = [1]

1. isSubtree(root, subRoot) 호출. root.val(1)과 subRoot.val(1)이 같음.
2. if 문에 진입하여 isSameTree(root, subRoot) 호출.
3. isSameTree([1, 1], [1])은 구조가 다르므로 false 반환.
4. isSubtree 함수가 이 false를 즉시 return 해버림. (실패)
5. (정답 로직) root.left (자식이 없는 [1])를 탐색했어야 함! isSubtree(root.left, subRoot)는 true였을 것이다.

4. 오늘의 교훈

• isSubtree 문제는 “탐색”과 “비교”라는 두 가지 다른 작업을 요구한다.
• “값이 같다”는 것은 “탐색을 시작할 후보”일 뿐이지, “유일한 정답 후보”가 아니다.
• isSameTree(root, sub)가 false라고 해서, isSubtree(root.left, sub)의 가능성까지 포기하면 안 된다.
• 재귀 함수를 짤 때는 OR로 연결해야 할 조건과 AND로 연결해야 할 조건을 명확히 구분하자.
  • isSameTree: left AND right
  • isSubtree: current OR left OR right