算法
分治
C++ 代码
#include<iostream>
#include<queue>
using namespace std;
int in[35], post[35];
struct Treenode
{
int val;
Treenode *left, *right;
Treenode(int v):val(v),left(NULL),right(NULL){}
};
Treenode* buildTree(int il,int ir,int pl,int pr)
{
if(il>ir)
return NULL;
int rval = post[pr];
Treenode *t = new Treenode(rval);
int pos = il;
while(in[pos]!=rval)
pos++;
int cnt = pos - il;
t->left = buildTree(il, pos - 1, pl, pl + cnt - 1);
t->right = buildTree(pos + 1, ir, pl + cnt, pr - 1);
return t;
}
void pre(Treenode *r)
{
if(r)
{
cout << r->val << endl;
pre(r->left);
pre(r->right);
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n;i++)
cin >> post[i];
for (int i = 1; i <= n;i++)
cin >> in[i];
Treenode *r = NULL;
r = buildTree(1, n, 1, n);
queue<Treenode *> q;
if(r)
q.push(r);
while(!q.empty())
{
Treenode* f = q.front();
q.pop();
cout << f->val << ' ';
if(f->left)
q.push(f->left);
if(f->right)
q.push(f->right);
}
return 0;
}