【信奥】收集树叶

1,287次阅读
没有评论

共计 597 个字符,预计需要花费 2 分钟才能阅读完成。

题面

描述

给出一棵二叉树,收集并移除所有叶子,重复执行,直到树为空

输入

第一行一个正整数n,表示结点的个数

n行,第i行第一个数l表示第i个结点左孩子的序号,第二个数r表示第i个结点右孩子的序号,-1表示空

输出

一共有若干行

请按照叶子的收集顺序,每收集一批叶子,将他们的序号打印在一行内

同一行内叶子的打印顺序为从左向右

思路

先求出每一个节点的高,用桶存入数组,再输出即可

【信奥】收集树叶

最终代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int l, r;
};
unordered_map<int,node> tree;
int n;
int ans=INT_MIN;
string res[10001];
int geth(int root)
{
	if (root == -1) return 0;
	int ll=geth(tree[root].l);
	int rr=geth(tree[root].r);
	int tmp = max(ll,rr)+1;
	res[tmp]+=(to_string(root)+" ");
	return tmp;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &tree[i].l, &tree[i].r);
	}
	int h=geth(1);
	for(int i=1;i<=h;i++)
	{
		cout<<res[i]<<endl;
	}
	return 0;
}
正文完
 
lvshujun
版权声明:本站原创文章,由 lvshujun 2020-06-09发表,共计597字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请联系站长并注明出处。
评论(没有评论)