PTA 列出叶结点 (25分)

PTA 列出叶结点
题目描述：

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。

输入格式：

首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-”。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

样例输出

4 1 5

这道题目呢，其实也算是一种套路，首先题目中说了从上到下，从左到右，你就应该想到，这就是层序遍历的套路呀，如果我能够找到层序遍历的数组，那么这个问题就迎刃而解了。

首先我们要明确一点，按照题目中的输入，根节点是肯定不会出现在这里面的，所以我们只需要找到没有出现的数字，然后就可以确定根节点，有了根节点，然后再模拟队列的性质，依次把他的左孩子，右孩子插入进来，然后遍历指针+1，继续插入根节点的左孩子的左孩子和右孩子…

那么问题来了，我需要用什么样的数据结构来存储这些内容呢？首先我得有一个树结点，但是这个结点呢，他不需要数据域，只需要一个左孩子和一个右孩子就可以了

struct Node
{
	int left;
	int right;
}

为什么要这么写呢？因为我一会儿会创建一个Node数组，数组的下标就是数据域，因此只需要保存每个结点的左右孩子就行了。

然后呢，我会用到一个辅助数组checked用来确定哪一个数字没有出现过，那就是根节点。

有了根节点，下一步我需要一个队列ans，首先把根节点存进去，然后从根节点开始，左孩子，右孩子，左孩子的（左孩子，右孩子），右孩子的（左孩子，右孩子）…，最后，遍历ans数组，如果有一个的 left 和 right 都是-1，那么说明这个就是叶结点。

#include <iostream>
#include <cstdio>
using namespace std;

struct Node
{
	int data;	
	int left;
	int right;
};
int main()
{
	int n;
	cin >> n;
	getchar();  //千万千万注意这个getchar(),否则程序会直接崩溃
	Node tree[15];   //因为这个数组的下标就是data，所以我不需要额外的data域
	int checked[15] = {};   //检查根节点的
	for(int i = 0;i < n;i++)
	{
		char l,r;	
		scanf("%c %c",&l,&r);
		getchar();  
		if(l == '-')tree[i].left = -1;
		else
		{
			tree[i].left = (l - '0');
			checked[l - '0'] = 1;
		}
		if(r == '-')tree[i].right = -1;
		else
		{
			tree[i].right = (r - '0');
			checked[r - '0'] = 1;
		}
	}
	int ans[15] = {};
	for(int i = 0;i < n;i++)
	{
		if(checked[i] == 0)
		{
			ans[0] = i;	//在这里找到了根节点，存进队列去了
			break;
		}
	}
	int k = 1;  //注意一下,k是从 1 开始的
	for(int i = 0;i < n;i++) 
	{
		if(tree[ans[i]].left != -1)ans[k++] = tree[ans[i]].left;	
		if(tree[ans[i]].right != -1)ans[k++] = tree[ans[i]].right;	
	}
	int flag = 0;
	for(int i = 0;i < n;i++)
	{
		if(tree[ans[i]].left == -1 && tree[ans[i]].right == -1)
		{
			if(flag)cout << " ";	
			flag = 1;
			cout << ans[i];
		}
	}
	return 0;
}