已知二叉树的后序遍历和中序遍历序列，构造对应的二叉树，并非递归前序遍历该二叉树。

#include
#include

using namespace std;

template
struct Node
{
type key;
bool visit;
Node *left, *right;
};

template
Node *CreatePreTree(type postorder[], int &n, type inorder[], int st, int e)
{
if(n < 1)
return NULL;

type key = postorder[n-1];
for(int i = st; i <= e; ++i)
{
if(key == inorder[i])
{
--n;
break;
}
}
Node *root = new Node;
root->key = key;
root->visit = false;

// right
if(e == i)
root->right = NULL;
else
root->right = CreatePreTree(postorder, n, inorder, i+1, e);

// left
if(st == i)
root->left = NULL;
else
root->left = CreatePreTree(postorder, n, inorder, st, i-1);
return root;
}

template
void PreOrderVisit(Node *root)
{
stack *> st;
st.push(root);
root->visit = true;
cout << root->key << " ";
while(!st.empty())
{
Node *t = st.top();
if(t->left && !(t->left->visit))
{
st.push(t->left);
t->left->visit = true;
cout << t->left->key << " ";
}
else if(t->right && !(t->right->visit))
{
st.push(t->right);
t->right->visit = true;
cout << t->right->key << " ";
}
else
{
st.pop();
}
}
}

template
void cleanup(Node *root)
{
if(root->left)
cleanup(root->left);
if(root->right)
cleanup(root->right);
delete root;
}

int main(int argc,char * argv[])
{
int postorder[] = {4, 7, 5, 2, 6, 3, 1};
int inorder[] = {4, 2, 7, 5, 1, 3, 6};
int n = 7;
Node *root = CreatePreTree(postorder, n, inorder, 0, 6);
PreOrderVisit(root);
cleanup(root);
return 0;
}