7-1 列出叶结点(25 分)ios
对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其全部叶节点。
输入格式:spa
首先第一行给出一个正整数 N(≤10),为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行,每行给出一个对应结点左右孩子的编号。若是某个孩子不存在,则在对应位置给出 “-“。编号间以 1 个空格分隔。
输出格式:code
在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:ip
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6string
输出样例:it
4 1 5io
思路
先找出 根节点 class
怎么找呢
能够想到 根节点 不会是任何一个结点的 儿子
那么 咱们只要标记一下 那些儿子 剩下的哪个 就是 根节点stream
而后从根节点 往下遍历cli
遍历到 一个结点 没有儿子的 那么就将它 push 进一个 vector
而后最后 输出就能够了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; const int MOD = 1e9 + 7; int v[10]; struct Node { int l, r; }q[10]; void init() { CLR(q); CLR(v); } queue <int> Q; vector <int> ans; void bfs() { int len = Q.size(); for (int i = 0; i < len; i++) { int num = Q.front(); Q.pop(); if (q[num].l == -1 && q[num].r == -1) ans.pb(num); if (q[num].l != -1) Q.push(q[num].l); if (q[num].r != -1) Q.push(q[num].r); } if (Q.size()) bfs(); } int main() { init(); int n; scanf("%d", &n); char a, b; for (int i = 0; i < n; i++) { scanf(" %c %c", &a, &b); if (a == '-') q[i].l = -1; else { q[i].l = a - '0'; v[a - '0'] = 1; } if (b == '-') q[i].r = -1; else { q[i].r = b - '0'; v[b - '0'] = 1; } } int root; for (int i = 0; i < n; i++) { if (v[i] == 0) { root = i; break; } } Q.push(root); bfs(); vector <int>::iterator it; for (it = ans.begin(); it != ans.end(); it++) { if (it != ans.begin()) printf(" "); printf("%d", *it); } cout << endl; }