求先序排列

链接

这题给出二叉树的中序序列和后序序列,要我们写出前序序列

我们可以通过递归调用中序序列和后序序列来构建完整的二叉树

接着直接输出前序序列,根据后序序列的特点,我们在中序序列中找到某一个根节点时,它对应的位置左边的子节点和后续序列位置相同,右节点同样相同

比如中序:BGDHAEFC 后序:GHDBFECA

A为根节点,在中序序列里,A的左边元素和后序前四个完全一样,A的右边和后序也完全一样(只有顺序不一样)

这是因为中序是左根右,而后序是左右根,也就是说,中序如果把根放在最后,元素就一样了,位置除外

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
struct TreeNode {
	char data;
	TreeNode* left, * right;
	TreeNode(char x) :data(x), left(nullptr), right(nullptr){}
};
TreeNode* buildTree(string& inorder, string& postorder, int inStart, int inEnd, 
	int PostStart, int postEnd, unordered_map<char, int>& inMap) {
	if (inStart > inEnd || PostStart > postEnd) {
		return nullptr;
	}
	char Val = postorder[postEnd];
	int inIndex = inMap[Val];
	int leftInsize = inIndex - inStart;
	TreeNode* root = new TreeNode(Val);
	root->left = buildTree(inorder, postorder, inStart, inIndex - 1, PostStart, PostStart + leftInsize - 1, inMap);
	root->right = buildTree(inorder, postorder, inIndex + 1, inEnd, PostStart + leftInsize, postEnd-1, inMap);
	return root;
}
void preorder(TreeNode* root) {
	if (!root) return;
	cout << root->data;
	preorder(root->left);
	preorder(root->right);
}
void deletetree(TreeNode* root) {
	if (!root) return;
	deletetree(root->left);
	deletetree(root->right);
	delete root;
}
int main() {
	string inorder = "BGDHAEFC";
	string postorder = "GHDBFECA";
	unordered_map<char, int>inMap;
	for (int i = 0;i < inorder.size();i++) {
		inMap[inorder[i]] = i;
	}
	TreeNode* root = buildTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, inMap);
	preorder(root);
	deletetree(root);
	root = nullptr;
	return 0;
}

时间复杂度:O(n)

空间复杂度:O(n)