후위 순회와 중위 순회를 통해 전위 순회 구하기

이 문제는 주어진 후위 순회(후순서)와 중위 순회(중간순서) 시퀀스로부터 원래의 이진 트리 구조를 재구성하고, 이를 바탕으로 전위 순회(전순서)를 얻는 것입니다. 핵심은 트리의 재귀적 구성 원리를 이해하는 데 있습니다.

1. 루트 노드 식별: 후위 순회에서 마지막 요소는 항상 현재 서브트리의 루트입니다.
2. 중위 순회에서 분할: 루트 값이 중위 순회에서 어디에 있는지 찾습니다. 그 위치 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리로 나뉩니다.
3. 왼쪽/오른쪽 서브트리 크기 계산: 중위 순회에서 루트 기준 왼쪽 요소 수를 세면, 후위 순회에서도 해당 개수만큼의 요소가 왼쪽 서브트리에 해당합니다.
4. 재귀적 구성: 왼쪽과 오른쪽 서브트리에 대해 각각 동일한 과정을 반복하여 노드를 생성하고 연결합니다.
5. 종료 조건: 중위 또는 후위 순회의 범위가 유효하지 않을 때(시작 인덱스 > 종료 인덱스), nullptr 반환하여 재귀 종료.

데이터 구조 선택: 링크드 구조 우선

• 배열 기반 저장은 완전 이진 트리에 유리하지만, 일반적인 이진 트리에서는 공간 낭비가 큼.
• 포인터 기반 구조(링크드 리스트 스타일)는 메모리 사용이 유연하며, 트리의 구조 변화에 유연하게 대응 가능.
• 각 노드는 다음과 같이 정의됨:

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

재귀 함수 설계

TreeNode* buildTree(int postIdx, int inStart, int inEnd, 
                     const std::unordered_map<int, int>& inIndexMap) {
    if (inStart > inEnd) return nullptr;

    int rootVal = post[postIdx];
    TreeNode* root = new TreeNode(rootVal);

    int rootInPos = inIndexMap.at(rootVal);
    int leftSubtreeSize = rootInPos - inStart;

    // 왼쪽 서브트리: 후위 순회에서 루트 앞에 있는 leftSubtreeSize개의 요소
    root->left = buildTree(postIdx - leftSubtreeSize - 1, inStart, rootInPos - 1, inIndexMap);

    // 오른쪽 서브트리: 후위 순회에서 루트 바로 앞부터 시작
    root->right = buildTree(postIdx - 1, rootInPos + 1, inEnd, inIndexMap);

    return root;
}

핵심 아이디어 정리

• 후위 순회의 마지막 요소 → 루트
• 중위 순회에서 루트 위치 → 왼쪽/오른쪽 서브트리 분리
• 왼쪽 서브트리 크기 → 후위 순회에서 왼쪽 부분 추출 기준
• 재귀 호출 시 인덱스 범위 조절로 서브트리 처리
• 범위가 무효하면 리턴 nullptr

사용 예시: 레벨 순서 탐색

생성된 트리의 레벨 순서 출력은 큐 기반 탐색으로 가능:

std::vector<int> levelTraversal(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        auto node = q.front(); q.pop();
        result.push_back(node->value);

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }

    return result;
}

주요 고려 사항

• 메모리 관리: new로 할당한 노드는 반드시 delete 해야 함 (실제 코드에서는 스마트 포인터 권장).
• 성능 최적화: 중위 순회의 값-인덱스 매핑을 미리 unordered_map에 저장해 검색 시간을 $O(1)$로 유지.
• 배열 인덱싱 규칙: 완전 이진 트리에서 부모-자식 관계는 $2i+1$, $2i+2$로 표현되지만, 일반 트리에서는 의미 없음.