Построение бинарного дерева из заданного предварительного и последующего порядка с использованием рекурсии

Question

Я делаю бинарное дерево в форме, заданной до и после заказа.

предварительный заказ: "vwbcyznamlp"

Пост-заказ: "cbznywmplav"

ЛОГИКА ДЛЯ ЭТОЙ ЦЕЛИ

V W B C Y Z N A M L P
C B Z N Y W M P L A V

Во-первых, обратите внимание, что корень - это V, потому что он первый в предварительном заказе и последний в почтовом заказе:

V W B C Y Z N A M L P
  C B Z N Y W M P L A V

Затем посмотрите на W и A, они, соответственно, они первый левый потомок и последний правый потомок корня. A в предзаказе обозначает место, где переход переходит от левого поддерева корня к правому поддереву корня. W в почтовом порядке отмечает то же место. Обратите внимание, что когда вы разделяете обходы, A и W являются смежными позициями:

V W B C Y Z N    A M L P
  C B Z N Y W    M P L A V

Теперь вам осталось решить ту же задачу для последовательностей:

W B C Y Z N    
C B Z N Y W

а также

A M L P
M P L A

Например, следующим шагом для первой последовательности будет:

W B C    Y Z N    
  C B    Z N Y W

Я делаю дерево с помощью рекурсии, но некоторые условия в рекурсии я не узнал. Поэтому, когда я пересекаю это дерево через преодер, тогда ответ был неправильным.

После создания дерева с помощью рекурсии ответ был

предварительный заказ: "vwbccyznaml"

Код, который я сделал, здесь

Сначала я сделал Tree Struct

  #include <iostream>
  #include <string>
  #include <stack>
  using namespace std;
  struct TreeNode
  {
  public:
   string enteredData;
   struct TreeNode *left;
   struct TreeNode *right;
   struct TreeNode* newNode(string data)
    {
     struct TreeNode* temp = new TreeNode();
     temp->enteredData = data;
     temp->left = temp->right = NULL;
     return temp;
   }
  };
  struct TreeNode* Buildingtree(string preorder, string postorder);

Дополнительные функции

//for returning tree
struct TreeNode *constructTree(string preorder, string postorder)
{
int preIndex = 0;
return Buildingtree(preorder, postorder);
}


//for pre-order traversal
void printPreorder(struct TreeNode* node)
{
if (node == NULL)
    return;
cout << node->enteredData << " ";
printPreorder(node->left);
printPreorder(node->right);
}


//for building tree from given preorder and postorder
struct TreeNode* Buildingtree(string preorder, string postorder)
{
string newPreoderForFunction = "";
string newPostoderForFunction = "";
struct TreeNode* root = new TreeNode();
string rightpreorder;
string rightpostorder;
static stack<string> u;
int indexForPreOder = 1;
int indexForPostOrder = postorder.length() - 2;
if (indexForPostOrder <= -1)
{
    string g;
    if (preorder != "")
        g.assign(1, preorder[0]);
    else
        g.assign(1, postorder[0]);
    root = root->newNode(g);
    return root;
 }
 else
 {
    string findingCharFromPreorder;
    findingCharFromPreorder.assign(1, preorder[indexForPreOder]);
    string findingCharFromPostorder;
    findingCharFromPostorder.assign(1, postorder[indexForPostOrder]);
    size_t found;
    string h = "";
    if (preorder != "")
        h.assign(1, preorder[0]);
    else if (postorder != "")
        h.assign(1, postorder[0]);
    root = root->newNode(h);
    if ((found = preorder.find(findingCharFromPostorder)) != string::npos)
    {
        newPreoderForFunction = preorder.substr(1, found - 1);
        rightpreorder = preorder.substr(found, preorder.length() - 1);
        u.push(rightpreorder);
    }
    if ((found = postorder.find(findingCharFromPreorder)) != string::npos)
    {

        newPostoderForFunction = postorder.substr(0, found + 1);

        rightpostorder = postorder.substr(found + 1, indexForPostOrder);

        if (rightpostorder.length() > 1)
            rightpostorder.erase(rightpostorder.length() - 1);
        u.push(rightpostorder);

    }
  }
  root->left = Buildingtree(newPreoderForFunction, newPostoderForFunction);
  string a;
  string b;
  a = u.top();
  u.pop();
  b = u.top();
  u.pop();
  root->right = Buildingtree(b, a);
  return root;
}

Основная функция

int main()
{
string a1 = "vwbcyznamlp";
string a2 = "cbznywmplav";
struct TreeNode *root = constructTree(a1,a2);
printPreorder(root);
cout << endl;
system("pause");
}