Language: C++

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

class Node
{
public:
    Node() {
        this->_id = 0;
        this->_left = 0;
        this->_right = 0;
        this->_parent = 0;
    }

    Node(int id) {
        this->_id = id;
        this->_left = 0;
        this->_right = 0;
        this->_parent = 0;
    }

    ~Node() {
        ;
    }

    // Accessor
    const int& id() const {
        return this->_id;
    }

    int& id() {
        return this->_id;
    }

    const int& left() const {
        return this->_left;
    }

    int& left() {
        return this->_left;
    }

    const int& right() const {
        return this->_right;
    }

    int& right() {
        return this->_right;
    }

    const int& parent() const {
        return this->_parent;
    }

    int& parent() {
        return this->_parent;
    }

private:
    int _id;
    int _left;
    int _right;
    int _parent;
};

std::vector<Node> nodelist;

void postorder(int id)
{
    int l = nodelist[id].left();
    int r = nodelist[id].right();
    if (l != 0)
        postorder(l);
    if (r != 0)
        postorder(r);
    cout << id << " ";

    return;
}

void maketree(std::vector<int>& pre, std::vector<int>& in)
{
    // cout << endl;

    int root = pre[0];

    std::vector<int> leftin;
    std::vector<int> rightin;

    // find root index in inorder
    auto rootitr = std::find(in.begin(), in.end(), root);

    // copy left and right subtrees
    std::copy(in.begin(), rootitr, std::back_inserter(leftin));
    std::copy(rootitr + 1, in.end(), std::back_inserter(rightin));

    // Debug print
    // cout << "pre-order : ";
    // for (int i = 0; i < pre.size(); i++) {
    //     cout << pre[i] << " ";
    // }
    // cout << endl;
    // cout << "in-order : ";
    // for (int i = 0; i < in.size(); i++) {
    //     cout << in[i] << " ";
    // }
    // cout << endl;
    // cout << "root = " << root << endl;
    // cout << "left subtree : ";
    // for (int i = 0; i < leftin.size(); i++) {
    //     cout << leftin[i] << " ";
    // }
    // cout << endl;
    // cout << "right subtree : ";
    // for (int i = 0; i < rightin.size(); i++) {
    //     cout << rightin[i] << " ";
    // }
    // cout << endl;

    // construct pre-order from two subtrees
    // pre-order of left subtree
    std::vector<int> leftpre;
    if (leftin.size() > 0) {
        int limin = *std::min_element(leftin.begin(), leftin.end());
        int limax = *std::max_element(leftin.begin(), leftin.end());
        std::copy(std::find(pre.begin(), pre.end(), limin),
                  std::find(pre.begin(), pre.end(), limax) + 1,
                  std::back_inserter(leftpre));
    }

    // pre-order of right subtree
    std::vector<int> rightpre;
    if (rightin.size() > 0) {
        int rimin = *std::min_element(rightin.begin(), rightin.end());
        int rimax = *std::max_element(rightin.begin(), rightin.end());
        std::copy(std::find(pre.begin(), pre.end(), rimin),
                  std::find(pre.begin(), pre.end(), rimax) + 1,
                  std::back_inserter(rightpre));
    }

    // Debug print
    // cout << "pre-order of left subtree : ";
    // for (int i = 0; i < leftpre.size(); i++) {
    //     cout << leftpre[i] << " ";
    // }
    // cout << endl;
    // cout << "pre-order of right subtree : ";
    // for (int i = 0; i < rightpre.size(); i++) {
    //     cout << rightpre[i] << " ";
    // }
    // cout << endl;

    // set children
    if (leftpre.size() > 0) {
        // cout << "Left child of " << root << " = " << leftpre[0] << endl;
        nodelist[root].left() = leftpre[0];
    }
    if (rightpre.size() > 0) {
        // cout << "Right child of " << root << " = " << rightpre[0] << endl;
        nodelist[root].right() = rightpre[0];
    }

    if (leftpre.size() > 1)
        maketree(leftpre, leftin);
    if (rightpre.size() > 1)
        maketree(rightpre, rightin);

    // cout << endl;
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;

    // initialize nodelist
    nodelist.resize(n + 1);

    std::vector<int> pre(n);
    std::vector<int> in(n);
    // input
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
        // set node id
        nodelist[i + 1].id() = i + 1;
    }
    for (int i = 0; i < n; i++) {
        cin >> in[i];
    }

    // construct tree
    maketree(pre, in);

    // Debug print
    // cout << endl;
    // for (int i = 1; i <= n; i++) {
    //     cout << "id: " << nodelist[i].id() << ", left: " << nodelist[i].left() << ", right: " << nodelist[i].right() << endl;
    // }

    // print post-order (argument is id of root)
    postorder(pre[0]);
    cout << endl;

    return 0;
}

Compiler output:
a.cc: In function 'void maketree(std::vector<int>&, std::vector<int>&)':
a.cc:94:29: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
   94 |     auto rootitr = std::find(in.begin(), in.end(), root);
      |                    ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/locale_facets.h:48,
                 from /usr/include/c++/14/bits/basic_ios.h:37,
                 from /usr/include/c++/14/ios:46,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:94:29: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
   94 |     auto rootitr = std::find(in.begin(), in.end(), root);
      |                    ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:127:27: error: 'min_element' is not a member of 'std'; did you mean 'tuple_element'?
  127 |         int limin = *std::min_element(leftin.begin(), leftin.end());
      |                           ^~~~~~~~~~~
      |                           tuple_element
a.cc:128:27: error: 'max_element' is not a member of 'std'; did you mean 'tuple_element'?
  128 |         int limax = *std::max_element(leftin.begin(), leftin.end());
      |                           ^~~~~~~~~~~
      |                           tuple_element
a.cc:129:28: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
  129 |         std::copy(std::find(pre.begin(), pre.end(), limin),
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:129:28: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  129 |         std::copy(std::find(pre.begin(), pre.end(), limin),
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:130:28: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
  130 |                   std::find(pre.begin(), pre.end(), limax) + 1,
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:130:28: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  130 |                   std::find(pre.begin(), pre.end(), limax) + 1,
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:137:27: error: 'min_element' is not a member of 'std'; did you mean 'tuple_element'?
  137 |         int rimin = *std::min_element(rightin.begin(), rightin.end());
      |                           ^~~~~~~~~~~
      |                           tuple_element
a.cc:138:27: error: 'max_element' is not a member of 'std'; did you mean 'tuple_element'?
  138 |         int rimax = *std::max_element(rightin.begin(), rightin.end());
      |                           ^~~~~~~~~~~
      |                           tuple_element
a.cc:139:28: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
  139 |         std::copy(std::find(pre.begin(), pre.end(), rimin),
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:139:28: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  139 |         std::copy(std::find(pre.begin(), pre.end(), rimin),
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:140:28: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
  140 |                   std::find(pre.begin(), pre.end(), rimax) + 1,
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:140:28: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  140 |                   std::find(pre.begin(), pre.end(), rimax) + 1,
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~