層序和中序重建二叉樹

• • 題目描述
  • Input Specification:
  • Output Specification:
  • Sample Input:
  • Sample Output:
  • 解題思路
  • Code

題目描述

輸入一棵二叉樹的層序和中序周遊，分别輸出其前序和後序周遊

Input Specification:

第一行輸入樹的大小，接下來一行給出樹的層序周遊，最後一行給出樹的中序周遊。

Output Specification:

第一行輸出其前序周遊，第二行輸出其後序周遊。

Sample Input:

8
1 2 7 3 6 5 9 4
2 1 5 3 9 7 4 6
           

Sample Output:

1 2 7 3 5 9 6 4
2 5 9 3 4 6 7 1
           

解題思路

在層序周遊中找到第一個沒被通路過且在對應的中序區間裡的結點，那麼這個結點就是目前的根結點，然後根據其在中序區間裡的位置分别劃分左右子樹，遞歸建樹。

測試的時候由于中序和後序複制了前序的代碼，而且忘了改，導緻一直調用前序周遊的部分結果，然後一直和我想的輸出不同，一度懷疑是重建出了問題。。。打死也不複制代碼了。。

Code

• AC代碼

#include<bits/stdc++.h>
using namespace std;
vector<int> lev, in;
struct Node{
	int val;
	struct Node *left, *right;
	Node(int _val):val(_val), left(NULL), right(NULL) {};
};
unordered_map<int, int> m;
Node *rebuildTree(int ll, int lr, int il, int ir) {
	if(il > ir) return NULL; 
	Node *root = NULL;
	int i, j;
	for(i = ll; i<=lr; i++) {
		if(m[lev[i]] == 1) continue;
		bool flag = false;
		for(j = il; j<=ir; j++) {
			if(lev[i] == in[j]) {
				flag = true;
				break;
			}
		}
		if(flag) {
			m[lev[i]] = 1;
			root = new Node(lev[i]);
			root->left = rebuildTree(ll, lr, il, j-1);
			root->right = rebuildTree(ll, lr, j+1, ir); 
			break;
		}
	}
	return root;
}
void preOrderT(Node *root) {
	if(!root) return ;
	cout << root->val << " "; 
	preOrderT(root->left);
	preOrderT(root->right);
}
void inOrderT(Node *root) {
	if(!root) return ;
	inOrderT(root->left);
	cout << root->val << " "; 
	inOrderT(root->right);
}
void postOrderT(Node *root) {
	if(!root) return ;
	postOrderT(root->left);
	postOrderT(root->right);
	cout << root->val << " "; 
} 
void bfs(Node *root) {
	queue<Node*> q;
	q.push(root);
	int curL = 1, nextL = 0;
	while(!q.empty()) {
		Node *cur = q.front();
		q.pop();
		curL--;
		cout << cur->val << " ";
		if(cur->left) {
			q.push(cur->left);
			nextL++;
		}
		if(cur->right) {
			q.push(cur->right);
			nextL++;
		}
		if(!curL) {
			curL = nextL;
			nextL = 0;
			cout << '\n';
		}
	}
}
int main() {
	freopen("in.txt", "r", stdin);
	int N;
	cin >> N;
	lev.resize(N);
	in.resize(N);
	for(int i = 0; i<N; i++) {
		cin >> lev[i];
	}
	for(int i = 0; i<N; i++) {
		cin >> in[i];
	}
	Node *root = rebuildTree(0, N-1, 0, N-1);
	preOrderT(root);
	cout << '\n';
	inOrderT(root);
	cout << '\n';
	postOrderT(root);
	cout << '\n';
	bfs(root);
	return 0;
}