7-4 List Leaves

发表于 更新于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

7-4 List Leaves
https://pintia.cn/problem-sets/16/problems/666

这道题就是根据给定的数据建立一棵树，然后从上到下、从左到右输出这棵树的叶子节点，属于基础题。
如果做过树的一些题，这道题的“种树”（构建树）应该会很简单：只需要按顺序建立一个结构体数组，在每个结构体中保存左右节点的下标。同时看哪一个节点没有被输入过，即是树的根节点（输入的节点是不同节点的孩子节点，只有根节点没有父节点）。
后面也很简单，只需要找出所有叶子节点，然后根据题目“in the order of top down, and left to right”的要求使用BFS，遍历过程中按顺序输出这些叶子节点即可。 

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using  node  = struct Node;
using tree = node * ;
struct Node
{
	int left;
	int right;
};

int root = -1;
vector<int> leaf;

vector<tree> create() {
	int n;
	cin >> n;
	vector<tree> nodes;
	vector<int> isRoot;
	for (auto i = 0; i < n; i++)
		isRoot.push_back(1);

	for (auto i = 0; i < n; i++) {
		char a, b;
		int left, right;
		cin >> a >> b;

		if (a == '-')
			left = -1;
		else {
			left = a - '0';
			isRoot[left] = 0;
		}
		if (b=='-')
			right = -1;
		else {
			right = b - '0';
			isRoot[right] = 0;
		}
		if (a=='-'&& b=='-')
		{
			leaf.push_back(i);
		}

		tree temp = new node;
		temp->left = left;
		temp->right = right;
		nodes.push_back(temp);
	}

	for (auto i = 0; i < n; i++)
	{
		if (isRoot[i] == 1)
		{
			root = i;
			break;
		}
	}
	return nodes;
}

void BFS(vector<tree> nodes) {
	queue<int> que;
	que.push(root);
	bool first = 1;
	while (!que.empty())
	{
		//弹出
		int f = que.front();
		que.pop();

		//处理
		for (auto x:leaf)
		{
			if (x == f)
			{
				if (!first)
				{
					cout << " ";
				}
				else
				{
					first = 0;
				}
				cout << x;
				break;
			}
		}

		//将左右节点加入队列
		if (-1 != nodes[f]->left)
		{
			que.push(nodes[f]->left);

		}
		if (-1 != nodes[f]->right)
		{
			que.push(nodes[f]->right);

		}
	}



}


int main()
{
	vector<tree> nodes = create();
	BFS(nodes);

	return 0;
}