L2-051 满树的遍历

题目 L2-051 满树的遍历

思路分析

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

int root;
vector<vector<int>> tree;
vector<bool> visited;
vector<int> ans;

void dfs(int root){
	ans.push_back(root);
	visited[root]=true;
	for(auto node:tree[root]){
		if(!visited[node]){
			dfs(node);
		}
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	tree.resize(n+1);
	visited.resize(n+1,false);
	for(int i=1;i<=n;i++){
		int fa;cin>>fa;
		if(fa==0)	root=i;
		tree[fa].push_back(i);
	}

	int MaxChildNum=-1;
	set<int> du;
	for(int i=1;i<=n;i++){
		int CurChildNum=tree[i].size();
		MaxChildNum=max(MaxChildNum,CurChildNum);
		if(CurChildNum>0) {
			du.insert(CurChildNum);
		}
	}

	cout<<MaxChildNum<<" ";

	// 可能存在度全为0的节点
	if(du.size()==0 || du.size()==1)	cout<<"yes"<<endl;
	else	cout<<"no"<<endl;

	dfs(root);

	cout<<ans[0];
	for(int i=1;i<n;i++)	cout<<" "<<ans[i];

	return 0;
}

同类题型

视频讲解

⬅️ multimap多值查询 🏠 00-天梯赛 ➡️ L2-052 吉利矩阵