杂题——满树的遍历

L2-3：满树的遍历

一棵“k 阶满树”是指树中所有非叶结点的度都是 k 的树。给定一棵树，你需要判断其是否为 k 阶满树，并输出其前序遍历序列。

注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。

输入格式：

输入首先在第一行给出一个正整数 n（≤105），是树中结点的个数。于是设所有结点从 1 到 n 编号。
随后 n 行，第 i 行（1≤i≤n）给出第 i 个结点的父结点编号。根结点没有父结点，则对应的父结点编号为 0。题目保证给出的是一棵合法多叉树，只有唯一根结点。

输出格式：

首先在一行中输出该树的度。如果输入的树是 k 阶满树，则加 1 个空格后输出 yes，否则输出 no。最后在第二行输出该树的前序遍历序列，数字间以 1 个空格分隔，行首尾不得有多余空格。
注意：兄弟结点按编号升序访问。

输入样例 1：

1
2
3
4
5
6
7
8
7
6
5
5
6
6
0
5

L2-3：满树的遍历
一棵“k 阶满树”是指树中所有非叶结点的度都是 k 的树。给定一棵树，你需要判断其是否为 k 阶满树，并输出其前序遍历序列。

注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。输出样例 1：

1
2
3 yes
6 1 4 5 2 3 7

输入样例 2：

1
2
3
4
5
6
7
8
7
6
5
5
6
6
0
4

输出样例 2：

1
2
3 no
6 1 4 7 5 2 3

代码长度限制

原题

思路

​ 一道经典的树的题目，使用vector来构造一颗树，随后我们就看看每个非叶子节点的度是否相同，随后先输出树的度（也就是所有节点度的最大值），然后如果所有非叶子节点的度相同，则输出yes，反之则输出no，最后再前序遍历一下这颗树就ok了。这里需要注意下这里的空格细节处理。否则会报一堆的格式错误。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int N = 1e5 + 10;
int n;
bool st[N];
vector<int> A[N];
bool flag;
string s;
void dfs(int k) {
    if (st[k]) return;
    st[k] = true;
    s += " " + to_string(k);
    for (auto kk : A[k]) {
        if (!st[kk]) {
            dfs(kk);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    int kk = 0;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        if (k) A[k].push_back(i);
        else kk = i;
    }

    for (int i = 1; i <= n; i++) {
        sort(A[i].begin(), A[i].end());
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int res = A[i].size();
        if (res != 0) {
            if (ans == 0) ans = res;
            else if (ans != res) {
                flag = true;
                ans = max(ans, res);
            }
        }
    }
    
    cout << ans << " ";
    if (flag) cout << "no\n";
    else cout << "yes\n";
    dfs(kk);
    cout << s.substr(1);
    return 0;
}