## L2-051 满树的遍历

题目链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1781658570803388426&page=1

题目分析：本题考的是**树的度+树的前序遍历**

1.树的度很好找，先记录每个节点的度，再找最大值就行，用**数组**就能完成

2.前序遍历就是正常的**递归函数**

解法代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
vector<int> res;
void pre_order(vector<vector<int>>& parent,int root,int n){
    if(res.size()==n){
        return;
    }
    res.push_back(root);
    for(auto& a:parent[root]){
        pre_order(parent,a,n);
    }
}
int main(){
    int n; cin>>n;
    vector<vector<int>> parent(n+1);//记录父节点，好计算度
    int root;
    for(int i=1;i<=n;i++){
        int p; cin>>p;
        if(p==0){
            root=i;
        }
        parent[p].push_back(i);
    }
    int degree=0;
    for(int i=1;i<=n;i++){
        if(parent[i].empty()){
            continue;
        }
        if(parent[i].size()>degree){
            degree=parent[i].size();
        }
        sort(parent[i].begin(),parent[i].end());
    }
    bool check=true;
    for(int i=1;i<=n;i++){
        if(parent[i].empty()){
            continue;
        }
        else{
            if(parent[i].size()!=degree){
                check=false;
                break;
            }
        }
    }
    pre_order(parent,root,n);
    cout<<degree<<" ";
    if(check){
        cout<<"yes"<<endl;
    }
    else{
        cout<<"no"<<endl;
    }
    for(int i=0;i<res.size();i++){
        if(i>0){
            cout<<" ";
        }
        cout<<res[i];
    }
    return 0;
}