《非常简单的一道题目》
就,如果你懂得关于树的知识,那么就确实就是很简单。题目都没有很难的,你觉得难是因为你的知识点不熟练。
满分代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+10;
int in[N],pre[N],n;
struct Node{
int l,r;
}Tree[N];
int build(int l1,int r1,int l2,int r2){
//l1-r1中序遍历,l2-r2先序遍历
if(l1 > r1 || l2 > r2) return 0;
int p = l1;
while(in[p] != pre[l2]) p++;
int len = p - l1;
int rt = pre[l2];
Tree[rt].l = build(l1,p-1,l2+1,l2 + len);
Tree[rt].r = build(p+1,r1,l2+len+1,r2);
return rt;
}
vector<int> ans;
void bfs(int s){
queue<int> que;
que.push(s);
while(!que.empty()){
int rt = que.front();
que.pop();
ans.push_back(rt);
int l = Tree[rt].l,r = Tree[rt].r;
if(r) que.push(r);
if(l) que.push(l);
}
}
int main()
{
cin>>n;
for(int i = 1;i <= n; ++i) cin>>in[i];
for(int i = 1;i <= n; ++i) cin>>pre[i];
build(1,n,1,n);
bfs(pre[1]);
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-1)cout<<" ";
}
return 0;
}
建树
建树就非常简单,就用结构体,一个l一个r就好了。
建树的思路:
1.先在中序中找到你当前树的根
int p = l1;
while(in[p] != pre[l2]) p++;
当前树指的是你当前树,因为之后可能会进入子树,那么当前树就变成了那个子树
而这个根已经给出来了,其实就是你当前树的
先序序列的第一个
2.求出左子树的长度
其实就是int len = p - l1
3.当前根的左孩子和右孩子递归求解
这里的参数呢,这四个分别是:
当前的
中序的第一个索引,中序的最后一个索引,先序的第一个索引,先序的最后一个索引
int rt = pre[l2];
Tree[rt].l = build(l1,p-1,l2+1,l2 + len);
Tree[rt].r = build(p+1,r1,l2+len+1,r2);
return rt;
4.特判,如果说你当前树递归下去发现了不合法(左大于右)那么就说明它不应该递归下去。它是一个叶子结点。
if(l1 > r1 || l2 > r2) return 0;
代码
int build(int l1,int r1,int l2,int r2){
//l1-r1中序遍历,l2-r2先序遍历
if(l1 > r1 || l2 > r2) return 0;
int p = l1;
while(in[p] != pre[l2]) p++;
int len = p - l1;
int rt = pre[l2];
Tree[rt].l = build(l1,p-1,l2+1,l2 + len);
Tree[rt].r = build(p+1,r1,l2+len+1,r2);
return rt;
}
层序遍历(用bfs)
就是说你要求层序遍历。最后的方法,正解,就是bfs。因为bfs好像从定义来看,就是一层一层地。其实就是完完全全的层序遍历的定义啊。
思路:
反正你的树已经建好了嘛。
那么你先把根放进去
之后按照先右结点再左结点的顺序去push进去
按照这个顺序去bfs就好了。
(注意,因为上面设置了叶子结点的左右都是0,所以你需要判断一下,如果是0的话,说明是叶子结点,那就不用放进去了)
代码
void bfs(int s){
queue<int> que;
que.push(s);
while(!que.empty()){
int rt = que.front();
que.pop();
ans.push_back(rt);
int l = Tree[rt].l,r = Tree[rt].r;
if(r) que.push(r);
if(l) que.push(l);
}
}
文章评论