(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.

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

根据后序遍历和中序遍历，还原二叉树，这是一道经典的数据结构题。

虽然很多人知道根据这两个序列能还原出二叉树，但是遇到题目还是会没有头绪。

这个题的核心思想是分而治之。

要构建一颗二叉树，无非就是构建它的根节点、左子树、右子树。

要构建左子树，无非就是构建左子树的根节点，左子树的左子树，左子树的右子树....以此类推

显然这是一个递归的过程。

假设我们定义一个函数build()用来构建树，只需要找到当前的根节点，然后让左子树和右子树重复执行build()就行。

本题的突破点是，后序遍历是先（递归地）访问左右节点，然后访问根节点，因此可以断定，最后一个节点一定是根节点！

比如有一条后序序列xxxxxxxxxxx，我们可以给它划分为
 

那么该如何确定左右子树的大小呢？这时就用到了中序遍历的特点。

中序遍历的顺序是左、中、右。例如有序列1 2 3 4 5 6 7，如果4是根节点的话，那么我们知道，不管1 2 3；5 6 7在树的内部是什么顺序，它们一定属于4的左、右子树。

我们可以定义函数build(pl_bound,pr_bound,il_bound,ir_bound)

其中pl_bound,pr_bound是后序遍历的左右边界下标，il_bound,ir_bound是中序遍历的左右边界下标。

那么显然 构建的过程可以由以下伪代码来模拟：

node build(pl_bound,pr_bound,il_bound,ir_bound){

        if(边界不符合要求)return nullptr;

        node root=new node();

        root.idx=pr_bound对应的后序数;

        root.left=build(左树所在的区间);

        root.right=build(右树所在的区间);

        return root;

}

以下是完整AC代码。层序遍历是一个简单的bfs。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <iomanip>
#include <sstream>
#include <queue>
using namespace std;
vector<int>postorder, inorder;
struct node {
	int idx = 0;
	node* lchild=nullptr, * rchild=nullptr;
};
node* build(int pl_bound, int pr_bound,int il_bound,int ir_bound) {
	//cout << "pl:" << pl_bound << " pr:" << pr_bound << " il:" << il_bound << " ir:" << ir_bound << endl;
	if (pl_bound > pr_bound)return nullptr;
	if (il_bound > ir_bound)return nullptr;
	//后序序列的最后一位一定是本树的根节点
	node* root = new node();
	root->idx = postorder[pr_bound];
	int l_size = 0, r_size = 0;//确定左右子树大小，分割后序序列的区间
	int inorder_idx = 0;//中序序列中该根节点的下标
	for (int i = il_bound; i <= ir_bound; ++i) {
		if (inorder[i] == root->idx) {
			l_size = i - il_bound;
			r_size = ir_bound - i;
			//这里容易混淆，因为ir_bound对应的是下标，会比实际大小少1，因此直接和i相减，刚好得到的就是去掉最右节点的右子树大小。
			inorder_idx = i;
			break;
		}
	}
	int l_rangel = pl_bound, l_ranger = l_rangel + l_size - 1;//左子树的左边界与原来相同，右边界由左子树大小确定
	int r_rangel = l_ranger + 1, r_ranger = r_rangel + r_size - 1;//同理
	root->lchild = build(l_rangel, l_ranger, il_bound, inorder_idx - 1);
	root->rchild = build(r_rangel, r_ranger,inorder_idx + 1,ir_bound);
	return root;


}
int main() {
	int n;
	cin >> n;
	postorder = vector<int>(n + 5);
	inorder = vector<int>(n + 5);
	for (int i = 0; i < n; ++i)cin >> postorder[i];
	for (int i = 0; i < n; ++i)cin >> inorder[i];
	node* head = build(0, n - 1, 0, n - 1);
	//bfs
	queue<node*>q;
	bool first = true;//第一个不输出空格，否则输出
	q.push(head);
	while (q.size()) {
		auto node = q.front();
		q.pop();
		if (!first)cout << " ";
		first = false;
		cout << node->idx;
		if (node->lchild)q.push(node->lchild);
		if (node->rchild)q.push(node->rchild);
	}
	return 0;
}