Cod sursa(job #2749851)

Utilizator DianaIfrosaIfrosa Diana DianaIfrosa Data 8 mai 2021 15:56:32
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("planeta.in");
ofstream fout("planeta.out");

struct nod
{
    int val;
    nod *stanga, *dreapta;

};

int n;
long long k;

vector <nod*> allBST(int stanga, int dreapta)
{
    //construiesc recursiv toti BST

    vector <nod*> bucati;
    if(stanga > dreapta)
        bucati.push_back(nullptr);

    else
    {
        //vor fi in ordine lexicografica pentru ca valorile se iau de la mic la mare
        for(int i=stanga; i<=dreapta; ++i) //iau fiecare nod pe rand si-l consider radacina
        {
            vector <nod*> subStanga=allBST(stanga,i-1);
            vector <nod*> subDreapta=allBST(i+1,dreapta);

            //conectez radacina cu subarborele stang si cu cel drept
            for(int j=0; j<subStanga.size(); ++j)
                for(int k=0; k<subDreapta.size(); ++k)
                {
                    nod* radacina=new nod();
                    radacina->val=i;
                    radacina->stanga=subStanga[j];
                    radacina->dreapta=subDreapta[k];

                    bucati.push_back(radacina);

                }

        }

    }

    return bucati;


}
void Preorder(nod * radacina)
{
    if(radacina!=nullptr)
    {
        fout<<radacina->val<<" ";
        Preorder(radacina->stanga);
        Preorder(radacina->dreapta);

    }
}

void allBstPreorders()
{

    vector <nod*> radacini=allBST(1,n);
    Preorder(radacini[k-1]); //indexarea de la 0

}

int main()
{

    fin>>n>>k;
    allBstPreorders();

    return 0;
}