Ch.6 트리 기초

면접실전 — 트리 Top 5 문제

트리 면접 빈출 Top 5 문제를 직접 풀어본다각 문제의 패턴과 최적 접근법을 정리한다

FAANG 트리 면접 Top 5를 정복하자

Max Depth, Invert Tree, Validate BST, LCA, Level Order Traversal — 이 5개만 완벽히 풀면 트리 면접의 80%를 커버합니다.

각각은 알겠는데, 실전에서 어떤 패턴을 적용할지 빠르게 판단할 수 있는가?

문제 유형 → 패턴 → 코드 파이프라인을 만들어봅시다.

article

핵심 내용

LeetCode #104 이진 트리의 최대 깊이를 구하라

패턴: 값 반환형 재귀 (Bottom-up) 핵심: max(왼쪽 깊이, 오른쪽 깊이) + 1 시간: O(n) | 공간: O(h)

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

# 면접 팁: 한 줄로 쓸 수도 있지만,
# 변수에 담아서 설명하는 것이 더 좋은 인상을 줍니다

면접관이 iterative로도 풀 수 있나요? 라고 물으면 BFS(레벨 순회)로 층 수를 세면 됩니다

LeetCode #226 이진 트리를 좌우 반전하라

패턴: 구조 변경형 재귀 핵심: 왼쪽 ↔ 오른쪽 swap 시간: O(n) | 공간: O(h)

def invertTree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

# 주의: swap을 동시에 해야 합니다 (Python tuple swap)
# 순서가 바뀌면 이미 변경된 포인터를 참조하게 됩니다

LeetCode #98 주어진 트리가 유효한 BST인지 검증하라

패턴: 범위 전달 재귀 핵심: (lo, hi) 범위를 좁혀가며 검증 함정: 직접 부모-자식만 비교하면 틀림! 시간: O(n) | 공간: O(h)

def isValidBST(root: TreeNode) -> bool:
    def validate(node, lo, hi):
        if not node:
            return True
        if node.val <= lo or node.val >= hi:
            return False
        return (validate(node.left, lo, node.val) and
                validate(node.right, node.val, hi))
    
    return validate(root, float('-inf'), float('inf'))

# 대안: 중위 순회하며 이전 값보다 항상 큰지 확인

LeetCode #236 두 노드의 최소 공통 조상을 찾아라

LCA란? 두 노드 p, q를 모두 자손으로 가지는 가장 깊은(가장 낮은) 조상 노드

def lowestCommonAncestor(root, p, q):
    # Base case
    if not root or root == p or root == q:
        return root
    
    # 왼쪽, 오른쪽에서 p, q를 찾는다
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # 양쪽에서 하나씩 찾았으면 → 현재가 LCA
    if left and right:
        return root
    
    # 한쪽에서만 찾았으면 → 그쪽이 LCA
    return left if left else right

# 시간: O(n), 공간: O(h)

LCA 핵심 아이디어 • p, q가 양쪽에 나뉘면 → 현재 노드가 LCA • p, q가 같은 쪽이면 → 그쪽에서 올라온 노드가 LCA • p(또는 q) 자체가 LCA일 수도 있음

이 문제는 재귀 + 분할정복의 정수. 면접에서 트리 사고력을 보여줄 최고의 문제입니다

LeetCode #102 트리를 레벨별로 묶어서 반환하라

패턴: BFS + 레벨 구분 핵심: 큐에서 현재 레벨 크기만큼 pop 시간: O(n) | 공간: O(n)

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)  # 현재 레벨의 노드 수
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

# 입력:    3
#         / \
#        9  20
#          /  \
#         15   7
# 출력: [[3], [9, 20], [15, 7]]

`level_size = len(queue)` — 이 한 줄이 레벨 구분의 핵심입니다. for 루프 안에서 큐에 자식을 추가해도 현재 레벨에는 영향 없습니다

5개 문제를 관통하는 3가지 패턴이 있습니다

패턴 1: Bottom-up 재귀 maxDepth, isBalanced, LCA → 리프에서 올라오며 답 계산 패턴 2: Top-down 재귀 invertTree, Validate BST → 루트에서 내려가며 상태 전달 패턴 3: BFS (Queue) Level Order, Zigzag, Right Side View → 층별 처리

문제를 보면 3가지 중 하나로 분류하세요. 패턴이 정해지면 코드는 자동으로 나옵니다

LCA 문제에서 p와 q가 양쪽 서브트리에 나뉘어 있으면 어떤 노드가 LCA인가?

Level Order Traversal에서 레벨을 구분하는 핵심 코드는?

Validate BST에서 직접 부모-자식 값만 비교하면 정확한 검증이 된다

edit_note

정리 노트

면접실전 — 트리 Top 5

3가지 패턴

Bottom-up: maxDepth, LCA, isBalanced
Top-down: invertTree, validateBST
BFS: levelOrder, zigzag

면접 필수 문제

#104: Max Depth — max(L,R)+1
#226: Invert — swap left/right
#98: Validate BST — (lo, hi) 범위
#236: LCA — left/right 분할
#102: Level Order — len(queue) 트릭

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작