拼题A 列出叶结点
程序员文章站
2022-07-15 08:33:39
...
拼题A 列出叶结点
题目描述
对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其所有叶节点。
输入格式:
首先第一行给出一个正整数 N(≤10),为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 “-”。编号间以 1 个空格分隔。
输出格式:
在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
输出样例:
4 1 5
沙雕的我直接用链表把题目给的树还原出来然后查找叶结点了。。。。
后来发现,emmm,,,不用这么麻烦(好像两种方法也差不多hhh)
两个版本都AC了~~
上代码:
版本一:链表还原版
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct Tree * TreeLink;
struct Tree
{
int data;
TreeLink left_tree, right_tree;
};
int n;
int ans[12];
bool is_root[12];
queue<TreeLink> q;
int main()
{
memset(is_root, true, sizeof(is_root));
cin >> n;
char l, r;
TreeLink *T;
T = (TreeLink *)malloc(sizeof(TreeLink) * 11);
for (int i = 0; i < n; i++) // 记得为每个结点分配内存空间
T[i] = (TreeLink)malloc(sizeof(struct Tree));
TreeLink root;
root = (TreeLink)malloc(sizeof(struct Tree));
for (int i = 0; i < n; i++)
{
getchar();
cin >> l >> r;
T[i]->data = i;
if (l == '-')
T[i]->left_tree = NULL;
if (r == '-')
T[i]->right_tree = NULL;
if (l != '-')
{
int ll = l - '0';
is_root[ll] = false;
T[i]->left_tree = T[ll];
}
if (r != '-')
{
int rr = r - '0';
is_root[rr] = false;
T[i]->right_tree = T[rr];
}
}
// 找根节点
int R;
for (int i = 0; i < n; i++)
{
if (is_root[i])
{
R = i;
break;
}
}
int sum = 0;
if (n > 0)
{
root = T[R];
q.push(root);
while (!q.empty())
{
TreeLink temp;
temp = q.front();
q.pop();
if (temp->left_tree == NULL && temp->right_tree == NULL)
ans[sum++] = temp->data;
if (temp->left_tree != NULL)
q.push(temp->left_tree);
if (temp->right_tree != NULL)
q.push(temp->right_tree);
}
}
for (int i = 0; i < sum; i++)
printf("%d%c", ans[i], i == sum - 1 ? '\n' : ' ');
return 0;
}
版本二:简练版
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct Tree
{
int data;
int left_tree, right_tree;
};
int n;
static int flag = 0;
void print(int n)
{
if(flag)
printf(" %d", n);
else
{
printf("%d", n);
flag = 1;
}
}
Tree T[12];
bool is_root[12];
queue<Tree> q;
int main()
{
memset(is_root, true, sizeof(is_root));
scanf("%d", &n);
char l, r;
for( int i = 0; i < n; i ++ )
{
getchar();
scanf("%c %c", &l, &r);
T[i].data = i;
if(l == '-')
T[i].left_tree = -1;
if(r == '-')
T[i].right_tree = -1;
if(l != '-')
{
int ll = l - '0';
T[i].left_tree = ll;
is_root[ll] = false;
}
if(r != '-')
{
int rr = r - '0';
T[i].right_tree = rr;
is_root[rr] = false;
}
}
// 找根节点
int root;
for( int i = 0; i < n; i ++ )
{
if(is_root[i])
{
root = i;
break;
}
}
if( n > 0 )
{
q.push(T[root]);
while(!q.empty())
{
Tree t = q.front();
q.pop();
if(t.left_tree == -1 && t.right_tree == -1)
print(t.data);
if(t.left_tree != -1)
q.push(T[t.left_tree]);
if(t.right_tree != -1)
q.push(T[t.right_tree]);
}
printf("\n");
}
return 0;
}
上一篇: Python之format字符串格式化