TREEORD

Link

#include <iostream>
using namespace std;

int preIndex = 0;
int postIndex = 0;

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

int findRootInInorder(int inorder[], int s, int e, int item)
{
for(int i = s; i <= e; i++)
{
if(inorder[i] == item)
{
return i;
}
}

return -1;
}

node * constructTree(int inorder[], int preorder[], int s, int e)
{
if(e < s)
{
return NULL;
}
//if there is only one element that must be root
if(e == s)
{
node *root = new node();
root->data = inorder[s];
root->left = root->right = NULL;
preIndex++;

return root;
}
else
{
int data = preorder[preIndex++];
node *root = new node();
root->data = data;

int index = findRootInInorder(inorder, s, e, data);
root->left = constructTree(inorder, preorder, s, index - 1);
root->right = constructTree(inorder, preorder, index + 1, e);

return root;

}

}


void getPostOrderTraversal(node *root, int temp[])
{
if(root)
{
printTree(root->left, temp);
printTree(root->right, temp);
temp[postIndex++] = root->data;
}
}

int main()
{
int n;
cin >> n;
int preorder[n], inorder[n], postorder[n], temp[n];
bool result = true;

for(int i = 0; i < n; i++)
{
cin >> preorder[i];
}

for(int i = 0; i < n; i++)
{
cin >> postorder[i];
}

for(int i = 0; i < n; i++)
{
cin >> inorder[i];
}

node *root = constructTree(inorder, preorder, 0, n - 1);

getPostOrderTraversal(root, temp);

    for(int i = 0; i < postIndex; i++)
{
        if(postorder[i] != temp[i])
        {
            result = false;
            break;
        }
}

if(result)
{
        cout << "yes\n";
}
else
{
        cout << "no\n";
}

return 0;
}