03-树2 List Leaves(25)

题目

分析

输入先给出结点的数量,把结点从0开始标号,每一行给出结点的左右两个子节点,-表示子节点不存在。

很容易分析出在子节点中没有出现的就是根节点,两个子节点都为空的是叶子节点

先建树,然后从root结点广度优先搜索,搜索到叶子节点就搜索,需要注意的是因为要求输出的顺序是从上到下、从左到右,因此如果左右子节点都不为空则应先push左子节点。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "bits/stdc++.h"
using namespace std;
struct TreeNode
{
int left, right;
}tree[14];
int main() {
int n, i;
cin >> n;
string l, r;
bool isRoot[14];
memset(isRoot, 1, sizeof(isRoot));
for (i = 0; i < n; i++) {
cin >> l >> r;
if (l[0] != '-') {
tree[i].left = stoi(l);
isRoot[tree[i].left] = 0;
}
else
tree[i].left = -1;
if (r[0] != '-') {
tree[i].right = stoi(r);
isRoot[tree[i].right] = 0;
}
else
tree[i].right = -1;
}
//找到根结点
int root;
for (i = 0; i < n; i++) {
if (isRoot[i]) root = i;
}
//cout << "根节点: " << root << endl;
queue<int> q;
q.push(root);
vector<int> v;
while (!q.empty()) {
int t = q.front();
//cout << t << ' ';
q.pop();
if (tree[t].left == -1 && tree[t].right == -1)
v.push_back(t);
if (tree[t].left != -1)
q.push(tree[t].left);
if (tree[t].right != -1)
q.push(tree[t].right);
}
//cout << endl;
for (i = 0; i < v.size(); i++) {
cout << v[i];
if (i != v.size() - 1)
cout << ' ';
}
return 0;
}

本文标题:03-树2 List Leaves(25)

文章作者:admin

发布时间:2017年10月11日 - 22:10

最后更新:2017年10月12日 - 12:10

原始链接:https://kxp555.coding.me/2017/10/11/PTA-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。