一遍AC祭

思路很抽象，按照结构体存储，因为先序遍历，所以输入建树后存下每个点的深度。

对于查询，倒序遍历深度大小，寻找深度等于目标深度的所有点，因为输入是先序的，所以易证遍历得到的顺序恰好等于该层遍历结果。

理论上层序遍历可以通过这种方式逃过队列。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e5+10;

struct node
{
	int fa,ch[2],value,deep;
};

int maxdep=0;
int idx;
node tree[N];

int input(int fa,int dep)
{
	int x;
	cin>>x;
	if(x==-1)
		return 0;
	int u=++idx;
	tree[u].fa=fa;
	maxdep=max(maxdep,dep);
	tree[u].deep=dep;
	tree[u].value=x;
	tree[u].ch[0]=input(u,dep+1);
	tree[u].ch[1]=input(u,dep+1);
	return u;
}

int main()
{
	int root=input(0,1);
	for(int i=maxdep;i>=1;i--)
	{
		for(int j=1;j<=idx;j++)
		{
			if(tree[j].deep==i)
				cout<<tree[j].value<<' ';
		}
		cout<<endl;
	}
	return 0;
}