天天看点

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

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;
}