글 읽기 - 이진트리에 대해 질문있습니다.(정답 코드 포함)

gogosky1175 3년 전 1

원래는 주석친 조건으로 제출했었는데 출력초과를 받았습니다. 그래서 조건을 수정해서 냈더니 답은 맞았습니다.

처음조건이 틀리는 이유를 생각해봤을 때 노드의 자식노드가 오른쪽 노드밖에 없을 때 일 것 같은데 이진트리는 자식노드를 왼쪽부터 가지지않나요?

제가 잘못이해하고있는 부분을 알려주시면 감사하겠습니다.

#include <iostream>
#include <vector>

using namespace std;
vector<int> in;
vector<int> post;

int n;

void pre(int inS, int inE, int postS, int postE)
{
    int inRoot{};
    if(postS <= postE)
    {
        cout << post[postE] << " ";
   
        //if(inS == inE && postS == postE)
        //   return;
    
        for(int i = 0; i < n; i++)
        {
            if(in[i] == post[postE])
            {
                inRoot = i;
                break;
            }
        }
    
        pre(inS, inRoot - 1, postS, postS + (inRoot - 1 - inS));
    
        //if(postS != postE - 1)
        pre(inRoot + 1, inE, postS + (inRoot - inS), postE - 1);
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    
    int t;
    
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        in.push_back(t);
    }
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        post.push_back(t);
    }
    
    pre(0, n - 1, 0, n - 1);
    cout<<'\n';
    
}

rihee1214 3년 전 1

이진트리는 자식노드가 두개 이하인 트리구조를 말합니다. 무조건적으로 자식 노드가 왼쪽부터 생성된다는 정의는 없습니다.

qw506799 3년 전 1

이진트리를 만들 때 루트보다 클 경우 오른쪽자식으로 작으면 왼쪽자식으로 만듭니다

무조건 왼쪽부터 생성되진 않아요

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

문제

문제

출처

ICPC

이진트리에 대해 질문있습니다.(정답 코드 포함)

gogosky1175 3년 전 1

rihee1214 3년 전 1

qw506799 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말