L2-3 满树的遍历
分数 25
全屏浏览
切换布局
作者 陈越
单位 浙江大学
一棵“k 阶满树”是指树中所有非叶结点的度都是 k 的树。给定一棵树，你需要判断其是否为 k 阶满树，并输出其前序遍历序列。
注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。
输入格式：
输入首先在第一行给出一个正整数 n（≤105），是树中结点的个数。于是设所有结点从 1 到 n 编号。
随后 n 行，第 i 行（1≤i≤n）给出第 i 个结点的父结点编号。根结点没有父结点，则对应的父结点编号为 0。题目保证给出的是一棵合法多叉树，只有唯一根结点。
输出格式：
首先在一行中输出该树的度。如果输入的树是 k 阶满树，则加 1 个空格后输出 yes，否则输出 no。最后在第二行输出该树的前序遍历序列，数字间以 1 个空格分隔，行首尾不得有多余空格。
注意：兄弟结点按编号升序访问。
输入样例 1：
7
6
5
5
6
6
0
5
输出样例 1：
3 yes
6 1 4 5 2 3 7
输入样例 2：
7
6
5
5
6
6
0
4
输出样例 2：
3 no
6 1 4 7 5 2 3
#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+8;
vector<int> tree[N],pre;
int maxt,root;
bool hefa=true;
void dfs(int x){
pre.push_back(x);
if(tree[x].size()==0)return;
if(tree[x].size()!=maxt)hefa=false;
for(int i=0;i<tree[x].size();i++){
dfs(tree[x][i]);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++){
int fu;cin>>fu;
if(fu==0){
root=i;
}else tree[fu].push_back(i);
}
maxt=tree[root].size();
dfs(root);
cout<<maxt<<" "<<(hefa?"yes\n":"no\n");
for(int i=0;i<pre.size();i++){
cout<<pre[i]<<" \n"[i==pre.size()-1];
}
}
