지우너

[코드트리] 트리 순회법 변경2, 3 C++ 본문

Problem Solving

[코드트리] 트리 순회법 변경2, 3 C++

지옹 2024. 10. 5. 20:00

전위 순회, 중위 순회가 주어졌을 때 후위 순회를 구하는 법 

https://www.codetree.ai/missions/9/problems/change-tree-traversal-2?&utm_source=clipboard&utm_medium=text

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> preorder;
vector<int> inorder;

vector<int> FindPostorder(int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
    // 범위를 벗어나는 경우
    if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
        return vector<int>();
    }

    // 1. 전위 순회의 첫 번째 노드는 루트
    // 2. 중위 순회에서 루트노드를 기준으로 왼쪽 노드들은 왼쪽 서브트리
    //                            오른쪽 노드들은 오른쪽 서브트리
    // 왼쪽 트리를 후위 순회한 결과, 오른쪽 트리를 후위 순회한 결과, 루트 노드를 재귀적으로 실행
    
    // 1. 전위 순회의 첫 번째 노드는 루트
    int root_val=preorder[preorderStart];
    int root_idx =0;
    for(int i=inorderStart; i<=inorderEnd; ++i){
        if(inorder[i]==root_val) {
            root_idx=i;
            break;
        }
    }

    // 재귀적으로 sub트리 구하기
    int left_size=root_idx-inorderStart;
    vector<int> leftSubtree=FindPostorder(preorderStart+1, preorderStart+left_size, inorderStart, root_idx-1 );
    vector<int> rightSubtree=FindPostorder(preorderStart+left_size+1, preorderEnd, root_idx+1, inorderEnd);

    // subtree 합치기
    vector<int> postorder;
    postorder.insert(postorder.end(), leftSubtree.begin(), leftSubtree.end());
    postorder.insert(postorder.end(), rightSubtree.begin(), rightSubtree.end());
    postorder.push_back(root_val);

    return postorder;
}

int main() {
    // input
    cin >> n;
    preorder.resize(n), inorder.resize(n);
    for(int i=0; i<n; ++i){
        cin >> preorder[i];
    }
    for(int i=0; i<n; ++i){
        cin >> inorder[i];
    }

    // solution
    vector<int> postorder = FindPostorder(0, n-1, 0, n-1);
    // output
    for(int i=0; i<n; ++i){
        cout << postorder[i] << " ";
    }
    return 0;
}

 

중위 순회, 후위 순회가 주어졌을 때 전위 순회를 구하는 법

https://www.codetree.ai/missions/9/problems/change-tree-traversal-3?&utm_source=clipboard&utm_medium=text

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> inorder;
vector<int> postorder;

//3
// 1 2 3 // 중위(왼 중 오) 
// 1 3 2 // 후위(왼 오 중)

vector<int> FindPreorder(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd){
    // 종료 조건
    if(inorderStart>inorderEnd || postorderStart>postorderEnd){
        return vector<int>();
    }

    int root_val= postorder[postorderEnd];
    // root가 중위 순회에서 어디에 있는지
    int root_idx=0;
    for(int i=inorderStart; i<=inorderEnd; ++i){
        if(inorder[i]==root_val){
            root_idx=i;
            break;
        }
    }
    
    int left_size=root_idx-inorderStart;
    vector<int> leftSubtree=FindPreorder(inorderStart, root_idx-1, postorderStart, postorderStart+left_size-1);
    vector<int> rightSubtree=FindPreorder(root_idx+1, inorderEnd, postorderStart+left_size, postorderEnd-1);

    vector<int> preorder; // 중 왼 오
    preorder.push_back(root_val);
    preorder.insert(preorder.end(), leftSubtree.begin(), leftSubtree.end());
    preorder.insert(preorder.end(), rightSubtree.begin(), rightSubtree.end());

    return preorder;
}

int main() {
    cin >> n;
    inorder.resize(n), postorder.resize(n);
    for(int i=0; i<n; ++i){
        cin >> inorder[i];
    }
    for(int i=0; i<n; ++i){
        cin >> postorder[i];
    }

    vector<int> preorder=FindPreorder(0, n-1, 0, n-1);

    for(int i=0; i<n; ++i){
        cout << preorder[i] << " ";
    }
    return 0;
}