完全二叉搜索树（中序遍历+存位置）
一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。
输入格式：
首先第一行给出一个正整数 N（≤1000），随后第二行给出 N 个不重复的非负整数。数字间以空格分隔，所有数字不超过 2000。
输出格式：
在一行中输出这棵树的层序遍历序列。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
10
1 2 3 4 5 6 7 8 9 0
输出样例：
6 3 8 1 5 7 9 0 2 4
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
const int N=1e3+10;
int n,a[N],ans[N];
int num=1;
void dfs(int u)
{
if(u>n) return;
dfs(u*2);
ans[u]=num++;
dfs(u*2+1);
}
int main()
{
cin>>n;
fir(i,1,n) cin>>a[i];
sort(a+1,a+1+n);
dfs(1);
int f=0;
fir(i,1,n)
{
if(f) cout<<" ";
f++;cout<<a[ans[i]];
}
return 0;
}
L2-004 这是二叉搜索树吗？（二叉搜索树性质+递归）
L2-004 这是二叉搜索树吗？
此题我们知道了二叉搜索树的性质：左子树小于根，右子树大于等于根。
且输入的是前序遍历，则对一个二叉树[l,r]：a[l]是根，[l+1,r]是左右子树范围。
其中，前x项若都小于根，剩下的都大于等于根：则从l+1开始的前x个就是左子树，剩下的都是右子树。如此就分出了左右子树[l1,r1][l2,r2]，然后再对左右子树递归即可。
由于输出要后序遍历，则我们只需：递归左子树，递归右子树，存根 （按照后序遍历的顺序）即可。
递归中注意一些范围。
镜像后的算法同理。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define pb push_back
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
const int N=1e3+10;
int n,a[N];
vector<int>ans;
int m;
void solve(int l,int r)//[l,r] 其中a[l]是根
{
if(r<l) return;
int i=l+1,j=r;
if(!m)
{
while(a[i]<a[l]&&i<=r) i++;
while(a[j]>=a[l]&&j>l) j--;
if(i-j!=1) return;
solve(l+1,i-1);
solve(j+1,r);
ans.pb(a[l]);
}
else
{
while(a[i]>=a[l]&&i<=r) i++;
while(a[j]<a[l]&&j>l) j--;
if(i-j!=1) return;
solve(l+1,i-1);
solve(j+1,r);
ans.pb(a[l]);
}
}
int main()
{
cin>>n;
fir(i,1,n) cin>>a[i];
m=0;//不镜像
solve(1,n);
if(ans.size()==n)
{
puts("YES");int f=0;
for(auto x:ans)
{
if(f) cout<<" ";
cout<<x;f++;
}
}
else
{
ans.clear();m=1;
solve(1,n);
if(ans.size()==n)
{
puts("YES");int f=0;
for(auto x:ans)
{
if(f) cout<<" ";
cout<<x;f++;
}
}
else puts("NO");
}
return 0;
}
L2-006 树的遍历（用后序和中序得出根节点、分出左右子树+递归）
L2-006 树的遍历
这里要用map，因为不知道这是什么形状的二叉树，不知道某个点是否有值。
后序的最后一个是根，用根在中序中分出左右子树，再递归地执行同样步骤。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))
const int N=30+10;
int n,hou[N],zhong[N];
map<int,int>mp;
void solve(int l,int r,int ll,int rr,int now)//后 中
{
//后序遍历则hou[r]是根
if(l<=r&&ll<=rr)
{
mp[now]=hou[r];
int root=hou[r];
for(int i=ll;i<=rr;i++)
{
if(zhong[i]==root)//找到根了
{
solve(l,i-1-ll+l,ll,i-1,now*2);
solve(r-rr+i,r-1,i+1,rr,now*2+1);
}
}
}
}
int main()
{
cin>>n;
fir(i,1,n) cin>>hou[i];
fir(i,1,n) cin>>zhong[i];
solve(1,n,1,n,1);
int f=0;
for(auto x:mp)
{
if(f) cout<<" ";
f++;
cout<<x.second;
}
return 0;
}
L2-011 玩转二叉树（中序+前序+递归）
L2-011 玩转二叉树
注意：前序中左子树范围的顺序其实就是左子树中根的顺序，右子树亦然。所以这里递归不需要中序的[l,r]，只需要知道根的位置。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))
const int N=30+10;
int n,z[N],q[N];
map<int,int>mp;
//中
void solve(int l,int r,int root,int now)
{
if(l<=r)
{
mp[now]=q[root];
for(int i=l;i<=r;i++)
{
if(q[root]==z[i])
{
solve(l,i-1,root+1,now*2+1);//左子树放到右边
solve(i+1,r,root+i+1-l,now*2);//右子树放到左边
return;
}
}
}
}
int main()
{
cin>>n;
fir(i,1,n) cin>>z[i];
fir(i,1,n) cin>>q[i];
solve(1,n,1,1);
int f=0;
for(auto x:mp)
{
if(f) cout<<" ";
f++;cout<<x.second;
}
return 0;
}
L2-035 完全二叉树的层序遍历（概念+递归）
L2-035 完全二叉树的层序遍历
根据完全二叉树和后序遍历概念递归。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=30+10;
int a[N],n;
map<int,int>mp;
int cnt;
void solve(int idx)
{
if(idx>n) return;
solve(idx*2);
solve(idx*2+1);
mp[idx]=a[cnt++];
}
int main()
{
cin>>n;
fir(i,1,n) cin>>a[i];
cnt=1;
solve(1);
int f=0;
for(auto x:mp)
{
if(f) cout<<" ";
if(x.second) cout<<x.second;
f++;
}
return 0;
}
