레야몬

[C++] 2263번 트리의 순회 - 트리, 분할 정복, 재귀 본문

알고리즘/백준

[C++] 2263번 트리의 순회 - 트리, 분할 정복, 재귀

Leyamon 2022. 9. 3. 16:51

#include <iostream>

#define MAX_VERTEX 100001

using namespace std;

int Index[MAX_VERTEX];
int io[MAX_VERTEX], po[MAX_VERTEX];
int n;

void f(int io_left, int io_right, int po_left, int po_right)
{
    if(io_left > io_right)
        return;
    
    int rootIndex = Index[po[po_right]];
    int ls = rootIndex - io_left;
    cout << io[rootIndex] << ' ';
    
    f(io_left, rootIndex-1, po_left, po_left+ls-1);
    f(rootIndex+1, io_right, po_left+ls, po_right-1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> io[i];
        Index[io[i]]=i;
    }
    for(int i=1; i<=n; i++)
        cin >> po[i];
        
    f(1, n, 1, n);
    
    return 0;
}

 

ㅈㄹ 어렵다.. 나에겐 아직 골드2는 버거운건가 참고한 사이트는 아래에 있다. 오랫만에 주석을 안적었는데.ㅠㅠ

 

 

<프리, 인, 포스트오더>

https://salguru.tistory.com/140

 

7장 트리 - (2) 트리의 순회

1. 트리의 순회(Tree Traversal) - 트리의 모든 노드를 방문하는 순서이다. - 그래프의 경우에는 DFS와 BFS가 있었다. - 트리에서도 위의 두 방법을 사용할 수 있지만, 트리에서만 사용할 수 있는 세 방법

salguru.tistory.com

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다

 
Comments