![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TPn1UeNpmT4VkeNBDOsJGcohVYsR2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLwYzNxEjM0MTMxAjMwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
- 对于后序序列,一个结点的访问总是先于这个结点的父结点的访问。可以利用这个结论,记录每个结点所有可能的父结点
,然后根据先序序列,配合使用栈,非递归地构造这棵树。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");
}
二刷:
- 先从先序遍历拿出第一个数作为根节点
- 获取后序遍历中根节点的前一个结点,查找他在先序遍历中的位置:
- 如果这个位置前一个位置是根,则该根只有一个子结点,说明它既可能是左子结点,也可能是右子结点,有多解
- 如果这个位置前一个位置不是根,说明它是根的右子树,而左子树是根的后面一个位置
#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;
}