中序 + 后序 序列建立二叉树

二叉树的建立

哈哈， 原本是数据结构的一道题，期末考试写出来了，到现在写题又给忘了，那咱们就来学一学吧！
7-11 浪漫侧影 (25 分)

“侧影”就是从左侧或者右侧去观察物体所看到的内容。

例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。

520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了……

我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。

例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。

于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。

输入格式：
输入第一行给出一个正整数 N (≤20)，为树中的结点个数。

随后在两行中先后给出树的中序遍历和后序遍历序列。

树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。

输出格式：
第一行输出右视图，第二行输出左视图，格式如样例所示。

输入样例：
8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1
输出样例：
R: 1 2 3 4 5
L: 1 6 7 8 5

AC代码， 详情见注释

#include "bits/stdc++.h"
using namespace std;
vector<int> z, h;

struct node{
	node *lchild;
	node *rchild;
	int val;
};
int p; // 指出当前所在的后序遍历位置 
node* build(node *root, int s, int e){
	if(s > e) return NULL;
	root = new node;
	root->lchild = root->rchild = NULL;
	root->val = h[p];
	int t;
	for(int i = s; i <= e; i++){ // 找到当前h[p] 在z中的位置
		if(z[i] == h[p]){
			t = i;
			break;
		}
	}
	p--; // 建完往下走
	if(s == e) return root;
	
	root->rchild = build(root, t + 1, e);// 递归建树
	root->lchild = build(root, s, t - 1); 
	
	return root;
}

void f(node *root){
	if(root == NULL) return;
	cout<<root->val<<endl;
	if(root->lchild != NULL) f(root->lchild);
	
	if(root->rchild != NULL) f(root->rchild);
	
}

int main(){
	
	int n;
	cin>>n;
	for(int i = 0; i < n; i++) {
		int d;
		cin>>d;
		z.push_back(d);
	}
	for(int i = 0; i < n; i++) {
		int d;
		cin>>d;
		h.push_back(d);
	}
	p = n - 1;
	node* root = NULL;
	root = build(root, 0, n - 1);
	// 左右视图用了一个二叉树的层序遍历分别取第一个和最后一个就是左视图和右视图
	queue<node*> q;
	q.push(root);
	vector<int> L, R;
	while(q.size()){  
		int d = q.size();
		vector<int> v; 
		for(int i = 0; i < d; i++){
			node* t = q.front();q.pop();
			v.push_back(t->val);
			if(t->lchild) q.push(t->lchild);
			if(t->rchild) q.push(t->rchild);
		}
		L.push_back(v[0]);
		R.push_back(v.back());
	}
    
	cout<<"R: ";
	for(int i = 0; i < R.size(); i++){
        if(i == 0)cout<<R[i];
		else cout<<" "<<R[i];
	}
    cout<<endl;
	cout<<"L: ";
	for(int i = 0; i < L.size(); i++){
		if(i == 0)cout<<L[0];
        else cout<<" "<<L[i];
	}
	
	return 0;
}
/*
8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1
*/