PAT甲级1020 Tree Traversals//由后序和中序序列确定一棵二叉树

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

翻译：假设二叉树中的所有键都是不同的正整数。给定后序遍历序列和中序遍历序列，应该输出相应二叉树的水平遍历序列。

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

翻译：每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数N（≤30），即二叉树中的节点总数。第二行给出后序序列，第三行给出中序序列。一行中的所有数字都用空格隔开。

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

翻译：对于每个测试用例，在一行中打印相应二叉树的水平顺序遍历序列。一行中的所有数字必须用一个空格隔开，并且行尾不能有多余的空格。

Sample Input:

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

思路

学过数据结构都知道直到后序序列和中序序列可以确定唯一一棵二叉树，因为后序序列能指出根结点，而中序序列能根据根结点区分其左子树和右子树。就比如题目给的样例

后序：2 3 1 5 7 6 4
中序：1 2 3 4 5 6 7
           

其中后序的最后一个4就是该树的根结点，而通过中序序列可知4的左子树包含1 2 3这三个结点，右子树包含5 6 7三个结点；此时再通过后序序列可知左子树的三个结点1 2 3中的根结点是1，再看中序可知以1为根结点没有左子树，而右子树包含2 3两个结点…以此类推最终建立起一棵树

4
      /   \
     1     6
      \   / \
       3 5   7
      /
     2
           

解题思路就是利用递归建树，用队列实现BFS水平遍历。

#include <iostream>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;
int in[50], post[50];
vector<int> vec;
struct node
{
	int val;
	node* left;
	node* right;
};
node* creat(int postL, int postR, int inL, int inR);
void BFS(node*);
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> post[i];
	for (int i = 0; i < n; i++)
		cin >> in[i];
	node* root = creat(0, n - 1, 0, n - 1);
	BFS(root);
	int flag = 0;
	for (int i = 0; i < vec.size(); i++)
	{
		if (flag == 1)
			cout << ' ';
		cout << vec[i];
		flag = 1;
	}
	system("pause");
	return 0;
}
node* creat(int postL, int postR, int inL, int inR)
{
	if (postL > postR) //递归边界，后序序列长度小于等于0则直接返回
		return NULL;
	node* root = new node;
	root -> val = post[postR]; //后序序列的最后一个结点就是当前二叉树的根结点
	int k = 0;
	for (int index = inL; index <= inR; index++) //在中序序列中找出这个根结点
		if (in[index] == post[postR])
			k = index;
	int num_left = k - inL; //num_left表示根节点左子树的结点数目
	root -> left = creat(postL, postL + num_left - 1, inL, k - 1);
	root -> right = creat(postL + num_left, postR - 1, k + 1, inR);
	return root;
}
void BFS(node* root)
{
	queue<node*> que;
	que.push(root);
	while (!que.empty())
	{
		int size = que.size();
		for (int i = 0; i < size; i++)
		{
			node* head = que.front();
			vec.push_back(head -> val);;
			if (head -> left != NULL)
				que.push(head -> left);
			if (head -> right != NULL)
				que.push(head -> right);
			que.pop();
		}
	}
}