1119 Pre- and Post-order Traversals (30分)

• 對于後序序列，一個結點的通路總是先于這個結點的父結點的通路。可以利用這個結論，記錄每個結點所有可能的父結點

  possibleParent

  ，然後根據先序序列，配合使用棧，非遞歸地構造這棵樹。
• 在建樹過程中，對于每個結點，從棧中找出所有可能的父結點，并将結點插入到相應位置（左子樹或右子樹）。
• 通過遞歸，在構造過程中形成分支。如果某次構造不可能完整地構造出整棵樹（沒有合适的位置插入結點），則進行回溯。
• 如果所有結點都已經被插入，則說明建樹成功。

#include<cstdio>
#include<unordered_set>
#include<stack>
#include<vector>
using namespace std;
int n, treeCount = 0;
int preorder[31], postorder[31];
unordered_set<int> possibleParent[10000];
vector<int> res;
struct node {
	int val;
	node *left, *right;
	node(int v) {
		val = v;
		left = NULL;
		right = NULL;
	}
}*root;

void inorderTraverse(node *cur) {
	if (cur == NULL)
		return;
	inorderTraverse(cur->left);
	res.push_back(cur->val);
	inorderTraverse(cur->right);
}

void buildTree(node *cur, stack<node*> st, int index) {
	if (index == n + 1) {	//建樹成功
		treeCount++;
		if (treeCount == 1) {
			inorderTraverse(root);
		}
		return;
	}
	if (possibleParent[preorder[index]].count(cur->val) != 0) {
		cur->left = new node(preorder[index]);
		st.push(cur->left);
		buildTree(cur->left, st, index + 1);
		cur->left = NULL;
		st.pop();	//cur->left
	}
	while (!st.empty()) {
		cur = st.top();
		st.pop();
		if (possibleParent[preorder[index]].count(cur->val) != 0) {
			cur->right = new node(preorder[index]);
			st.push(cur->right);
			buildTree(cur->right, st, index + 1);
			cur->right = NULL;
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1;i <= n;i++) {
		scanf("%d", &preorder[i]);
	}
	for (int i = 1;i <= n;i++) {
		scanf("%d", &postorder[i]);
	}
	for (int i = 1;i <= n;i++) {
		int j = n;
		while (postorder[j] != preorder[i]) {
			possibleParent[preorder[i]].insert(postorder[j]);
			j--;
		}
	}
	root = new node(preorder[1]);	//根節點
	node *cur = root;
	stack<node*> st;
	st.push(cur);
	buildTree(cur, st, 2);
	if (treeCount <= 1) {
		printf("Yes\n");
	}
	else printf("No\n");
	for (int i = 0;i < res.size();i++) {
		if (i != 0)
			printf(" ");
		printf("%d", res[i]);
	}
	printf("\n");
}
           

二刷：

1. 先從先序周遊拿出第一個數作為根節點
2. 擷取後序周遊中根節點的前一個結點，查找他在先序周遊中的位置:
3. 如果這個位置前一個位置是根，則該根隻有一個子結點，說明它既可能是左子結點，也可能是右子結點，有多解
4. 如果這個位置前一個位置不是根，說明它是根的右子樹，而左子樹是根的後面一個位置

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n;
vector<int> preorder, postorder, inorder;
struct node {
	int val, size;
	node *left, *right;
	node(int v) {
		val = v;
		left = NULL;
		right = NULL;
	}
}*root = NULL;
unordered_map<int, int> preIndex, postIndex;
unordered_set<int> inserted;	//某個元素是否已經插入了
bool unique = true;
void insert(node *&cur, int val) {
	cur = new node(val);
	inserted.insert(val);
	int valPostIndex = postIndex[val];
	if (valPostIndex == 0 || inserted.count(postorder[valPostIndex - 1]) != 0) {	//沒有子結點了
		return;
	}
	int childVal = postorder[postIndex[val] - 1], childPreIndex = preIndex[childVal];
	if (preorder[childPreIndex - 1] == val) {	//情況3，cur隻有一個子結點
		unique = false;
		insert(cur->left, childVal);	//多解時子結點預設放到左子結點
	}
	else {
		insert(cur->left, preorder[preIndex[val] + 1]);
		insert(cur->right, childVal);
	}
}
void inorderTraverse(node *cur) {
	if (cur == NULL) {
		return;
	}
	inorderTraverse(cur->left);
	inorder.push_back(cur->val);
	inorderTraverse(cur->right);
}
int main() {
	cin >> n;
	preorder.resize(n);
	postorder.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> preorder[i];
		preIndex[preorder[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		cin >> postorder[i];
		postIndex[postorder[i]] = i;
	}

	insert(root, preorder[0]);
	inorderTraverse(root);
	if (unique) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
	for (int i = 0; i < n; i++) {
		if (i != 0) {
			cout << " ";
		}
		cout << inorder[i];
	}
	cout << endl;
}
           

簡化：不用真的把樹構造出來，隻需要将“儲存結點”這個操作安排在适當的位置，插入函數在遞歸調用中就能形成中序序列。

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n;
vector<int> preorder, postorder, inorder;
unordered_map<int, int> preIndex, postIndex;
unordered_set<int> inserted;	//某個元素是否已經插入了
bool unique = true;
void insert(int val) {
	inserted.insert(val);
	int valPostIndex = postIndex[val];
	if (valPostIndex == 0 || inserted.count(postorder[valPostIndex - 1]) != 0) {	//沒有子結點了
		inorder.push_back(val);
		return;
	}
	int childVal = postorder[postIndex[val] - 1], childPreIndex = preIndex[childVal];
	if (preorder[childPreIndex - 1] == val) {	//情況3，cur隻有一個子結點
		unique = false;
		inorder.push_back(val);
		insert(childVal);
	}
	else {
		insert(preorder[preIndex[val] + 1]);
		inorder.push_back(val);
		insert(childVal);
	}
}
int main() {
	cin >> n;
	preorder.resize(n);
	postorder.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> preorder[i];
		preIndex[preorder[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		cin >> postorder[i];
		postIndex[postorder[i]] = i;
	}

	insert(preorder[0]);
	if (unique) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
	for (int i = 0; i < n; i++) {
		if (i != 0) {
			cout << " ";
		}
		cout << inorder[i];
	}
	cout << endl;
}