本文最后更新于 506 天前,其中的信息可能已经有所发展或是发生改变。
题面
描述
给出一棵二叉树,收集并移除所有叶子,重复执行,直到树为空
输入
第一行一个正整数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; }