给定一个二叉树的中序和层序输出,重建二叉树并按先序和后序输出。
#include#includeusing namespace std;
struct TreeNode {
int data;
TreeNode* leftchild;
TreeNode* rightchild;
TreeNode(int n) {
data = n;
}
};
vectorceng;
vectormid;
vectorpre;
vectorpost;
TreeNode* BuildTree(int cl, int cr, int ml, int mr);
void preOrder(TreeNode* r);
void PostOrder(TreeNode* r);
int main() {
int num;
cin >>num;
int temp;
for (int i = 0; i< num; i++) {
cin >>temp;
ceng.push_back(temp);
}
for (int i = 0; i< num; i++) {
cin >>temp;
mid.push_back(temp);
}
TreeNode* root = BuildTree(0, num - 1, 0, num - 1);
preOrder(root);
PostOrder(root);
for (int i = 0; i< num - 1; i++) {
cout<< pre[i]<<" ";
}
cout<< pre[num - 1]<< endl;
for (int i = 0; i< num - 1; i++) {
cout<< post[i]<< " ";
}
cout<< post[num - 1]<< endl;
}
TreeNode* BuildTree(int cl, int cr, int ml, int mr)
{
if(ml>mr)
return nullptr;
int i, j;
int cnt = 0;
for (i = cl; i<= cr; i++) {
for ( j = ml; j<= mr; j++) {
if (ceng[i] == mid[j]) {
cnt = 1;
break;
}
}
if (cnt == 1)
break;
}
TreeNode* r = new TreeNode(ceng[i]);
r->leftchild = BuildTree(cl + 1, cr, ml, j - 1);
r->rightchild = BuildTree(cl + 1, cr, j + 1, mr);
return r;
}
void preOrder(TreeNode* r)
{
if (r == NULL)
return;
pre.push_back(r->data);
preOrder(r->leftchild);
preOrder(r->rightchild);
}
void PostOrder(TreeNode* r)
{
if (r == NULL)
return;
PostOrder(r->leftchild);
PostOrder(r->rightchild);
post.push_back(r->data);
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧