还原二叉树 【中序+层序重建二叉树】

题目大意：给出二叉树的层序遍历和中序遍历，要求输出先序遍历和后序遍历。

分析：

1、由层序遍历和中序遍历直接重建二叉树。

2、由层序遍历和中序遍历我们先递归求出先序序列，再由先序和中序重建二叉树。自己一开始犯了个致命的小错误记录下，在循环外面int j之后在里面又脑残的 int 了一次j(可能是手残）导致一直WA。。TAT

代码1：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
int layer[50], in[50], pre[50];
int n,idx=0;
struct Node{
	int data;
	Node *lchild,*rchild;
};

//由层序遍历和中序遍历重建二叉树 
Node* Create(int ll, int lr, int inl, int inr){
	if(inl>inr)
		return NULL;
	Node *root = new Node;
	int i,j;
	bool f;
	for(i = ll; i<=lr; i++){
		f = false;
		for(j = inl; j<=inr; j++){
			if(layer[i] == in[j]){
				root->data = in[j];
				root->lchild = NULL;
				root->rchild = NULL;
				f = true;
				break;
			}
		}
		if(f) break;
	}
	if(!f) return NULL;
	if(j > inl) root->lchild = Create(0, n-1, inl, j-1);
	if(j < inr) root->rchild = Create(0, n-1, j+1, inr);
	return root;
}

void preOrder(Node *root){
	if(root == NULL) return;
	printf("%d", root->data);
	idx++;
	if(idx != n) printf(" ");
	preOrder(root->lchild);
	preOrder(root->rchild);
}

void inOrder(Node *root){
	if(root == NULL) return;
	inOrder(root->lchild);
	printf("%d", root->data);
	idx++;
	if(idx != n) printf(" ");
	inOrder(root->rchild);
}

void postOrder(Node *root){
	if(root == NULL) return;
	postOrder(root->lchild);
	postOrder(root->rchild);
	printf("%d", root->data);
	idx++;
	if(idx != n) printf(" ");
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i<n; i++)
		scanf("%d", &layer[i]);
	for(int i = 0; i<n; i++)
		scanf("%d", &in[i]);
	Node *root = Create(0, n-1, 0, n-1);
	idx = 0;
	preOrder(root);
	printf("\n");
	idx=0; 
	postOrder(root); 
	return 0;
}
           

代码2：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
int layer[maxn], in[maxn], pre[maxn];
int n,idx=0;
struct Node{
	int data;
	Node *lchild,*rchild;
};

void cal(int ll, int lr, int inl, int inr){
	int i,j;
	//找出层序遍历中的根节点在中序序列中的位置 
	for(i = ll; i<=lr; i++){
		bool f = false;
		for(j = inl; j<=inr; j++){//由{}里面的是局部变量，和外面的变量名无关，因此之前在此处又int j导致一直WA。。 
			if(layer[i] == in[j]){
				pre[idx++] = in[j];//构造先序序列 
				f = true;
				break;
			}
		}
		if(f) break;
	}
	//左子树存在的话 
	if(j>inl) cal(ll, lr, inl, j-1);
	//右子树存在的话 
	if(j<inr) cal(ll, lr, j+1, inr);
}
//由先序和中序递归构造二叉树 
Node* Create(int pl, int pr, int inl, int inr){
	if(inl > inr) return NULL;
	int k = inl;
	while(k<inr && in[k] != pre[pl]) k++;
	Node *node = new Node;
	node->data = pre[pl];
	int num = k-inl;
	node->lchild = Create(pl+1, pl+num, inl, k-1);
	node->rchild = Create(pl+num+1, pr, k+1, inr);
	return node;
}
//先序遍历 
void preOrder(Node *root){
	if(root == NULL) return;
	printf("%d", root->data);
	idx++;
	if(idx != n) printf(" ");
	preOrder(root->lchild);
	preOrder(root->rchild);
}
//中序遍历 
void inOrder(Node *root){
	if(root == NULL) return;
	inOrder(root->lchild);
	printf("%d", root->data);
	idx++;
	if(idx != n) printf(" ");
	inOrder(root->rchild);
}
//后序遍历 
void postOrder(Node *root){
	if(root == NULL) return;
	postOrder(root->lchild);
	postOrder(root->rchild);
	printf("%d", root->data);
	idx++;
	if(idx != n) printf(" ");
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i<n; i++)
		scanf("%d", &layer[i]);
	for(int i = 0; i<n; i++)
		scanf("%d", &in[i]);
	cal(0, n-1, 0, n-1);
	Node *root = Create(0, n-1, 0, n-1);
	idx=0;
	preOrder(root);
	printf("\n");
	idx = 0;
	postOrder(root); 
	return 0;
}