当前位置：首页 > news >正文

二叉树【2.5】代码专项

news 来源：原创 2024/9/20 10:46:00

醍醐灌顶——node* root 和node* &root作为参数的区别

return value：

写一个前序遍历的（使用指针）

中序遍历，只改动了preorder，只调换了一行

后序

层序（使用bfs），新建队列和vector

二叉树的层数

输出所有二叉树节点的层号

翻转二叉树，并且输出反转后的先序&中序序列编辑

注意，此处向上，难度评级都是：简单！！！！！！！！>-<

还原二叉树

醍醐灌顶——node* root 和node* &root作为参数的区别

插入节点时有引用，而搜索时只有指针没有引用

先中后序遍历亦然，因为只是遍历或者修改节点data，不用引用，

新建节点、改变树的结构需要引用

return value：

3221225477 (0xC0000005): 访问越界，一般是读或写了野指针指向的内存。

3221225725 (0xC00000FD): 堆栈溢出，一般是无穷递归造成的。

return value 3221225725

3221225620 (0xC0000094): 除0错误，一般发生在整型数据除了0的时候。

我说为何报错说是野指针了，因为没有new申请空间

写一个前序遍历的（使用指针）

写半天写不对，才发现，自己构造节点可以输出正确的序列（中序亦然）

所以是节点的读入有问题

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;
};
node* tree[N];void preorder(node* root)
{//递归边界：NULL
if(root == NULL)
return;
//遍历
printf("%d ",root->id ); 
preorder(root->lchild);
preorder(root->rchild);}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;
//	scanf("%d",&n);node* root=NULL;bool flag=0;
//	for(int i=0;i<n;i++)
//	{
//		int l,r;
//		scanf("%d %d",&l,&r);
//			tree[i]=newnode(i);
//		if(!flag && (l!=-1||r!=-1))
//		{
//			flag=1;
//			root=tree[i];
//			//root->id=i;
//		}
//			if(l!=-1)tree[l]=newnode(l),tree[i]->lchild=tree[l];
//			if(r!=-1)tree[r]=newnode(r),tree[i]->rchild=tree[r];
//	}
//	int i=0;
node* n0=newnode(0);
node* n1=newnode(1);
node* n2=newnode(2);
node* n3=newnode(3);
node* n4=newnode(4);
node* n5=newnode(5);
n0->lchild=n2;n0->rchild=n5;n5->rchild=n3;n2->lchild=n1;n2->rchild=n4;//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;preorder(n0);	
}

后来我发现了问题，你是边写变创建节点的，可能4一开始被你连上2，但是后来又被你新建new，2-》lchild还是4，但4的孩子在别的地址了，因为new又申请了别的空间

所以我一开始就把n个节点统统创建好？

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;
};
node* tree[N];void preorder(node* root)
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
printf("%d ",root->id ); 
preorder(root->lchild);
preorder(root->rchild);}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}
//	int i=0;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=2;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=5;
//	cout<<"node="<<tree[i]->id<<"rchild="<<tree[i]->rchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//cout<<tree[0]->rchild->rchild->id;preorder(root);	
}//node* n0=newnode(0);
//node* n1=newnode(1);
//node* n2=newnode(2);
//node* n3=newnode(3);
//node* n4=newnode(4);
//node* n5=newnode(5);
//n0->lchild=n2;n0->rchild=n5;n5->rchild=n3;n2->lchild=n1;n2->rchild=n4;

答案对了但格式错误，因为末尾不能有多余的空格

所以新建一个vector存储他们吧

ac了（）

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;
};
node* tree[N];
vector<int> ans;
void preorder(node* root)
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}
//	int i=0;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=2;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=5;
//	cout<<"node="<<tree[i]->id<<"rchild="<<tree[i]->rchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//cout<<tree[0]->rchild->rchild->id;preorder(root);	
for(int i=0;i<ans.size();i++)
{printf("%d",ans[i]);
if(i<ans.size()-1) printf(" ");
}
}//node* n0=newnode(0);
//node* n1=newnode(1);
//node* n2=newnode(2);
//node* n3=newnode(3);
//node* n4=newnode(4);
//node* n5=newnode(5);
//n0->lchild=n2;n0->rchild=n5;n5->rchild=n3;n2->lchild=n1;n2->rchild=n4;

中序遍历，只改动了preorder，只调换了一行

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;
};
node* tree[N];
vector<int> ans;
void preorder(node* root)
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
preorder(root->lchild);
ans.push_back(root->id) ;
preorder(root->rchild);}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}preorder(root);	
for(int i=0;i<ans.size();i++)
{printf("%d",ans[i]);
if(i<ans.size()-1) printf(" ");
}
}

后序

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;
};
node* tree[N];
vector<int> ans;
void preorder(node* root)
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
preorder(root->lchild);preorder(root->rchild);ans.push_back(root->id) ;
}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}preorder(root);	
for(int i=0;i<ans.size();i++)
{printf("%d",ans[i]);
if(i<ans.size()-1) printf(" ");
}
}

层序（使用bfs），新建队列和vector

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;
};
node* tree[N];
vector<int> ans;
void preorder(node* root)//前序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
queue<node*> q;
void layorder(node *root)
{q.push(root);while(!q.empty()){//ans.push_back(->id);node* temp=q.front();ans.push_back(temp->id);q.pop();if(temp->lchild!=NULL) q.push(temp->lchild);if(temp->rchild!=NULL) q.push(temp->rchild);}}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}
//	int i=0;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=2;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=5;
//	cout<<"node="<<tree[i]->id<<"rchild="<<tree[i]->rchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//cout<<tree[0]->rchild->rchild->id;layorder(root);	
for(int i=0;i<ans.size();i++)
{printf("%d",ans[i]);
if(i<ans.size()-1) printf(" ");
}
}//node* n0=newnode(0);
//node* n1=newnode(1);
//node* n2=newnode(2);
//node* n3=newnode(3);
//node* n4=newnode(4);
//node* n5=newnode(5);
//n0->lchild=n2;n0->rchild=n5;n5->rchild=n3;n2->lchild=n1;n2->rchild=n4;

二叉树的层数

我：在层序的基础上，添加layer计数，广度遍历完，答案就出来了

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;int lay;
};
node* tree[N];
vector<int> ans;
void preorder(node* root)//前序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
queue<node*> q;
int ans_layer=1;
void layorder(node *root)
{q.push(root);while(!q.empty()){//ans.push_back(->id);node* temp=q.front();ans.push_back(temp->id);q.pop();if(temp->lchild!=NULL) temp->lchild->lay=temp->lay+1,q.push(temp->lchild), ans_layer=temp->lay+1;if(temp->rchild!=NULL) temp->rchild->lay=temp->lay+1,q.push(temp->rchild), ans_layer=temp->lay+1;}}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}
//	int i=0;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=2;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=5;
//	cout<<"node="<<tree[i]->id<<"rchild="<<tree[i]->rchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//cout<<tree[0]->rchild->rchild->id;root->lay =1;	
layorder(root);	
//for(int i=0;i<ans.size();i++)
//{printf("%d",ans[i]);
//if(i<ans.size()-1) printf(" ");
//}
printf("%d",ans_layer);
}//node* n0=newnode(0);
//node* n1=newnode(1);
//node* n2=newnode(2);
//node* n3=newnode(3);
//node* n4=newnode(4);
//node* n5=newnode(5);
//n0->lchild=n2;n0->rchild=n5;n5->rchild=n3;n2->lchild=n1;n2->rchild=n4;

答案：递归求解

height=max（left 子树height，right子树height）+1

输出所有二叉树节点的层号

因为我刚才已经算出来了，只需输出即可

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;int lay;
};
node* tree[N];
vector<int> ans;
void preorder(node* root)//前序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
queue<node*> q;
int ans_layer=1;
void layorder(node *root)
{q.push(root);while(!q.empty()){//ans.push_back(->id);node* temp=q.front();ans.push_back(temp->id);q.pop();if(temp->lchild!=NULL) temp->lchild->lay=temp->lay+1,q.push(temp->lchild), ans_layer=temp->lay+1;if(temp->rchild!=NULL) temp->rchild->lay=temp->lay+1,q.push(temp->rchild), ans_layer=temp->lay+1;}}
node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}
//	int i=0;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=2;
//	cout<<"node="<<tree[i]->id<<"lchild="<<tree[i]->lchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//	 i=5;
//	cout<<"node="<<tree[i]->id<<"rchild="<<tree[i]->rchild->id<<"rchild="<<tree[i]->rchild->id<<endl;
//cout<<tree[0]->rchild->rchild->id;root->lay =1;	
layorder(root);	
//for(int i=0;i<ans.size();i++)
//{printf("%d",ans[i]);
//if(i<ans.size()-1) printf(" ");
//}
for(int i=0;i<n-1;i++)
printf("%d ",tree[i]->lay );
printf("%d",tree[n-1]->lay );}//node* n0=newnode(0);
//node* n1=newnode(1);
//node* n2=newnode(2);
//node* n3=newnode(3);
//node* n4=newnode(4);
//node* n5=newnode(5);
//n0->lchild=n2;n0->rchild=n5;n5->rchild=n3;n2->lchild=n1;n2->rchild=n4;

翻转二叉树，并且输出反转后的先序&中序序列

我：翻转函数写了半天，其实就是递归的将所有节点的左孩子与有孩子对调

并且递归顺序与执行顺序无关

即

void rvs(node* &root)
{if(root==NULL) return;node* tp=new node;tp=root->lchild;root->lchild =root->rchild;root->rchild =tp;rvs(root->lchild);rvs(root->rchild);}

和

void rvs(node* &root)
{if(root==NULL) return;node* tp=new node;rvs(root->lchild);rvs(root->rchild);tp=root->lchild;root->lchild =root->rchild;root->rchild =tp;}

都能ac

附完整代码

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;int lay;
};
node* tree[N];
vector<int> ans1,ans2;
void preorder(node* root)//前序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans1.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
void midorder(node* root)//中序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
midorder(root->lchild);
ans2.push_back(root->id) ;
midorder(root->rchild);}void rvs(node* &root)
{if(root==NULL) return;node* tp=new node;tp=root->lchild;root->lchild =root->rchild;root->rchild =tp;rvs(root->lchild);rvs(root->rchild);}node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}root->lay =1;	
rvs(root);
preorder(root);	
for(int i=0;i<ans1.size();i++)
{printf("%d",ans1[i]);
if(i<ans1.size()-1) printf(" ");
}
printf("\n");
midorder(root);	
for(int i=0;i<ans2.size();i++)
{printf("%d",ans2[i]);
if(i<ans2.size()-1) printf(" ");
}
//for(int i=0;i<n-1;i++)
//printf("%d ",tree[i]->lay );
//printf("%d ",tree[n-1]->lay );}

答案的思路也是一样，但是用的静态数

并且使用swap进行交换。

试了，指针也可以swap

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1005;
struct node
{node* lchild;node* rchild;int data;int id;int lay;
};
node* tree[N];
vector<int> ans1,ans2;
void preorder(node* root)//前序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans1.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
void midorder(node* root)//中序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
midorder(root->lchild);
ans2.push_back(root->id) ;
midorder(root->rchild);}void rvs(node* &root)
{if(root==NULL) return;node* tp=new node;
swap(root->lchild ,root->rchild );rvs(root->lchild);rvs(root->rchild);}node* newnode(int id1)
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}
int main()
{int n;scanf("%d",&n);node* root=NULL;bool flag=0;for(int i=0;i<n;i++) tree[i]=newnode(i);for(int i=0;i<n;i++){int l,r;scanf("%d %d",&l,&r);//tree[i]=newnode(i);if(!flag && (l!=-1||r!=-1)){flag=1;root=tree[i];//root->id=i;}if(l!=-1)//tree[l]=newnode(l),tree[i]->lchild=tree[l];if(r!=-1)//tree[r]=newnode(r),tree[i]->rchild=tree[r];}root->lay =1;	
rvs(root);
preorder(root);	
for(int i=0;i<ans1.size();i++)
{printf("%d",ans1[i]);
if(i<ans1.size()-1) printf(" ");
}
printf("\n");
midorder(root);	
for(int i=0;i<ans2.size();i++)
{printf("%d",ans2[i]);
if(i<ans2.size()-1) printf(" ");
}
//for(int i=0;i<n-1;i++)
//printf("%d ",tree[i]->lay );
//printf("%d ",tree[n-1]->lay );}

标程

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 50;
struct Node {int l, r;
} nodes[MAXN];
vector<int> pre, in, post;
void preOrder(int root) {if (root == -1) {return;}pre.push_back(root);preOrder(nodes[root].l);preOrder(nodes[root].r);
}
void inOrder(int root) {if (root == -1) {return;}inOrder(nodes[root].l);in.push_back(root);inOrder(nodes[root].r);
}
void revert(int root) {if (root == -1) {return;}revert(nodes[root].l);revert(nodes[root].r);swap(nodes[root].l, nodes[root].r);
}
int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &nodes[i].l, &nodes[i].r);}revert(0);preOrder(0);inOrder(0);for (int i = 0; i < (int)pre.size(); i++) {printf("%d", pre[i]);if (i < (int)pre.size() - 1) {printf(" ");}}printf("\n");for (int i = 0; i < (int)in.size(); i++) {printf("%d", in[i]);if (i < (int)in.size() - 1) {printf(" ");}}return 0;
}

注意，此处向上，难度评级都是：简单！！！！！！！！>-<

还原二叉树

先序中序=》后序

这玩意必须递归写，

核心就是：给你两个区间，你返回根节点，最后自下而上构成一棵树，最终的返回值是最上面的根节点

#include<stdio.h>
#include<bits/stdc++.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1005;int n;int s1[N],s2[N];
struct node
{node* lchild;node* rchild;int data;int id;int lay;
};
node* tree[N];
vector<int> ans1,ans2,ans3;
void preorder(node* root)//前序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
ans1.push_back(root->id) ;
preorder(root->lchild);
preorder(root->rchild);}
void midorder(node* root)//中序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
midorder(root->lchild);
ans2.push_back(root->id) ;
midorder(root->rchild);}
void nxtorder(node* root)//后序遍历 
{//递归边界：NULL
if(root == NULL)
{//printf("=null");
return;}//遍历
//printf("%d ",root->id ); 
nxtorder(root->lchild);
nxtorder(root->rchild);
ans3.push_back(root->id) ;}
node* newnode(int id1)//新建节点 
{node* Node=new node;Node->id =id1;Node->lchild=NULL;Node->rchild=NULL;return Node;
}node* create(int a1,int b1,int a2,int b2)//前序的左右端点，中序的左右端点，返回值是根节点 
{if(a1>b1 ||a2>b2) return NULL;//注意return NULL，表示自己就是空节点，且不再递归 node* root=newnode(s1[a1]);int k;for(int i=0;i<n;i++){	if(s2[a2+i]==s1[a1]){k=i;break;	}	}root->lchild =create(a1+1,a1+k,a2,a2+k-1);root->rchild =create(a1+k+1,b1,a2+k+1,b2);return root; 
}
int main()
{scanf("%d",&n);node* root=new node;for(int i=0;i<n;i++)	{scanf("%d",&s1[i]);	 } for(int i=0;i<n;i++)	{scanf("%d",&s2[i]);	 } root=create(0,n-1,0,n-1);
//preorder(root);	//输出前序 
//for(int i=0;i<ans1.size();i++)
//{printf("%d",ans1[i]);
//if(i<ans1.size()-1) printf(" ");
//}
//printf("\n");
//midorder(root);	//输出中序
//for(int i=0;i<ans2.size();i++)
//{printf("%d",ans2[i]);
//if(i<ans2.size()-1) printf(" ");
//}
nxtorder(root);	//输出后序
for(int i=0;i<ans3.size();i++)
{printf("%d",ans3[i]);
if(i<ans3.size()-1) printf(" ");
}
//for(int i=0;i<n-1;i++)
//printf("%d ",tree[i]->lay );
//printf("%d ",tree[n-1]->lay );}

解析