알고리즘 기록 제12일 [이진 트리]

1. LeetCode 226. 이진 트리 뒤집기

주어진 이진 트리의 루트 노드를 기준으로 트리를 완전히 뒤집은 후, 새로운 루트를 반환하세요.

입력: root = [4,2,7,1,3,6,9]
출력: [4,7,2,9,6,3,1]

문제 링크

핵심 접근 방식:

• 재귀적 뒤집기: 현재 노드와 그 자식들을 순차적으로 처리하며 트리 전체를 재귀적으로 뒤집습니다.
• 자식 교환: 각 재귀 호출에서 왼쪽과 오른쪽 서브트리를 직접 교환함으로써 구조를 반전시킵니다.

TreeNode* invertTree(TreeNode* node) {
    if (node == nullptr) return node;
    std::swap(node->left, node->right);
    invertTree(node->left);
    invertTree(node->right);
    return node;
}

정리

재귀 종료 조건을 명확히 설정하면, 나머지 로직은 자연스럽게 작동합니다.

2. LeetCode 101. 대칭 이진 트리 확인

이진 트리의 루트가 주어질 때, 해당 트리가 좌우 대칭인지 판단하세요.

예시 1:
입력: root = [1,2,2,3,4,4,3]
출력: true

문제 링크

핵심 접근 방식:

• 재귀적 비교: 왼쪽과 오른쪽 서브트리의 구조와 값이 일치하는지 단계별로 비교합니다.
• 종료 조건 명시: 빈 노드가 등장할 경우 올바르게 처리되도록 조건을 정의합니다.
• 값 및 구조 검증: 구조뿐 아니라 노드 값도 동일해야만 대칭이라고 판단합니다.
• 대칭적 비교 전략: 왼쪽 서브트리의 내부(오른쪽 자식)와 오른쪽 서브트리의 내부(왼쪽 자식)를 비교합니다.

bool checkSymmetry(TreeNode* leftNode, TreeNode* rightNode) {
    if (leftNode == nullptr && rightNode != nullptr) return false;
    if (leftNode != nullptr && rightNode == nullptr) return false;
    if (leftNode == nullptr && rightNode == nullptr) return true;
    if (leftNode->val != rightNode->val) return false;

    bool innerMatch = checkSymmetry(leftNode->right, rightNode->left);
    bool outerMatch = checkSymmetry(leftNode->left, rightNode->right);

    return innerMatch && outerMatch;
}

bool isSymmetric(TreeNode* root) {
    if (root == nullptr) return true;
    return checkSymmetry(root->left, root->right);
}

정리

대칭성 판단 시, 왼쪽의 오른쪽 자식과 오른쪽의 왼쪽 자식을 비교하는 것이 핵심입니다.

3. LeetCode 104. 이진 트리의 최대 깊이

이진 트리의 루트가 주어졌을 때, 가장 긴 경로에 포함된 노드 수를 반환하세요.

예시 1:
입력: root = [3,9,20,null,null,15,7]
출력: 3

문제 링크

핵심 접근 방식:

• 재귀 깊이 계산: 트리의 깊이를 재귀적으로 계산합니다.
• 기저 사례 처리: 루트가 비어 있는 경우 깊이 0을 반환합니다.
• 서브트리 깊이 비교: 왼쪽과 오른쪽 자식의 깊이 중 더 큰 값을 선택합니다.
• 깊이 누적: 현재 노드는 깊이에 +1을 추가하여 계산합니다.

int calculateDepth(TreeNode* node) {
    if (node == nullptr) return 0;
    int depthLeft = calculateDepth(node->left);
    int depthRight = calculateDepth(node->right);
    return std::max(depthLeft, depthRight) + 1;
}

int maxDepth(TreeNode* root) {
    return calculateDepth(root);
}

정리

왼쪽과 오른쪽 서브트리의 깊이를 비교해 최댓값을 반환하면 됩니다.

4. LeetCode 111. 이진 트리의 최소 깊이

루트에서 가장 가까운 리프 노드까지의 최단 경로에 포함된 노드 수를 반환하세요.

참고: 리프 노드는 자식이 없는 노드입니다.
예시 1:
입력: root = [3,9,20,null,null,15,7]
출력: 2

문제 링크

핵심 접근 방식:

• 재귀적 최소 깊이 계산: 트리의 깊이를 재귀적으로 탐색합니다.
• 빈 노드 처리: 루트가 비어 있으면 깊이 0을 반환합니다.
• 단방향 서브트리 처리: 한쪽 자식만 존재할 경우, 그 쪽의 깊이를 기준으로 계산합니다.
• 최소값 반환: 두 자식 모두 존재하면, 둘 중 작은 깊이에 +1을 더합니다.

int findMinDepth(TreeNode* node) {
    if (node == nullptr) return 0;

    int leftDepth = findMinDepth(node->left);
    int rightDepth = findMinDepth(node->right);

    // 한쪽에만 자식이 있는 경우
    if (node->left == nullptr && node->right != nullptr) {
        return rightDepth + 1;
    }
    if (node->left != nullptr && node->right == nullptr) {
        return leftDepth + 1;
    }

    // 양쪽 모두 존재하는 경우
    return std::min(leftDepth, rightDepth) + 1;
}

int minDepth(TreeNode* root) {
    return findMinDepth(root);
}

정리

한쪽 자식만 존재하는 경우, 그 방향의 깊이를 기준으로 삼아야 하며, 리프 노드까지의 최단 경로만 고려해야 합니다.