[백준] 4256번 : 트리 - 재귀

https://www.acmicpc.net/problem/4256

4256번: 트리

1. 문제설명

트리의 전위순회 결과와 중위순회 결과를 바탕으로 트리의 구조를 구해낼 수 있고,

이를 후위순회한 결과를 출력하는 문제이다.

 

전위 순회한 결과 먼저오는 노드가 루트노드임을 알 수 있고,

그 루트노드를 바탕으로 중위순회 결과를 보면

해당 루트노드의 왼쪽 서브트리와 오른쪽 서브트리를 알 수 있다.

 

이를 재귀적으로 구현하면 트리 구조를 구현할 수 있고,

이를 후위순회하면  정답이 된다.

 

 

 

 

 

2. 문제풀이코드

#include <bits/stdc++.h>
using namespace std;

int n,pidx, preOrderRes[1001], inOrderRes[1001], order[1001];

struct Node{
    int data;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int _data, Node* _left, Node* _right): data(_data), left(_left), right(_right){}
};


void postOrder(Node* root){
    if(root== nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << ' ';
}

void deconstruct(Node* root){
    if(root == nullptr) return;
    deconstruct(root->left);
    deconstruct(root->right);
    root = nullptr;
    delete root;
}


Node* makeTree(int start, int end){
    if(start > end) return nullptr;
    
    Node* newNode = new Node(preOrderRes[pidx++], nullptr, nullptr);
    if(start==end) return newNode;
    int mid = order[newNode->data];
    newNode->left = makeTree(start, mid-1);
    newNode->right = makeTree(mid+1, end);
    return newNode;
}

void makeTree(Node** root){
    pidx = 1;
    *root = makeTree(1, n);
}



int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;
    for(int T=0; T<t; T++){
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> preOrderRes[i];
        }
        for(int i=1; i<=n; i++){
            cin >> inOrderRes[i];
            order[inOrderRes[i]] = i;
        }
        Node *root = nullptr;

        makeTree(&root);
        postOrder(root);
        cout << '\n';
        deconstruct(root);
    }

    return 0;
}