글 읽기 - 메모리 초과 도와주실 분

kjuny00 2년 전 0

정답 코드를 보지 않아서 제가 푼 방식이 틀렸을지 잘 모르겠지만 우선 제 풀이를 설명해보자면
Post order의 뒤에서 부터 하나씩 route를 세우면서 그 노드를 기준으로 인오더에서 오른쪽이면 재귀로 오른자식으로 세우고
다 끝난 뒤에도 주어진 범위에서 남아있으면 왼쪽 자식으로 재귀를 하는식으로 만들었습니다.
처음에는 그냥 벡터 슬라이싱으로 매개변수를 주었는데 메모리 초과가 떠서 질문 게시판의 조언대로 index를 주는식으로 바꿔봤는데도
또 메모리 초과가 떠서 질문 드립니다.
질문 게시판에 있는 반례들과 제가 몇 개 트리 만들어서 해봤을 때에는 다 정답이 나와가지고 어디서 잘못되었는지 잘 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

stack<int> poord;
vector<int> inorder;

struct node
{
    int numb;
    node* left;
    node* right;
};

void maketree(node* root, int start, int end){
    if (end - start == 1 || poord.empty())
        return;
    auto rindex = find(inorder.begin()+ start, inorder.begin() + end, root->numb) - inorder.begin() - start;
    if ( end- start - rindex > 1){
        node* child = new node;
        child->numb = poord.top();
        poord.pop();
        root->right = child;
        maketree(child, start+rindex +1, end);
    }
    if (poord.empty())
        return;
    if (find(inorder.begin()+start, inorder.begin()+end,poord.top()) != inorder.begin()+end ){
        node* child = new node;
        child->numb = poord.top();
        poord.pop();
        root->left = child;
        maketree(child, start, start+rindex);
    }
    return;
    
}

void preorder(node* root){

    if (root == nullptr)
        return;
    cout << root->numb << " ";
    auto left = root->left;
    auto right = root->right;
    delete root;
    preorder(left);
    preorder(right);
    return;
}

int main() {
    int n, k;
    cin >> n;
    for (int i =0 ; i< n; i++){
        cin >> k;
        inorder.push_back(k);
    }
    for (int i  =0 ; i< n; i++){
        cin >> k;
        poord.push(k);
    }
    node* root = new node;
    root->numb = poord.top();
    poord.pop();
    maketree(root, 0, inorder.end() - inorder.begin());
    preorder(root);

    return 0;
} 

kjuny00 2년 전 0

처음 struct node에서 left 와 right의 기본값을 nullptr로 해줬더니 맞았네요..

왜 그런걸까요..?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과 도와주실 분

kjuny00 2년 전 0

kjuny00 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말