A1138 Postorder Traversal (前序中序转后序)

Postorder Traversal (前序中序转后序)"/>

A1138 Postorder Traversal (前序中序转后序)

原题：

参考柳如大佬的

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include<stack>
#include<queue>
#include<sstream>
using namespace std;/*
A1138 Postorder Traversal (25 分)
我开始以为后序第一个和中序一样，后来想想不一样
*/
const int MaxN = 50010;int pre[MaxN], in[MaxN];
int N;
vector <int> post;void ToPost(int preL, int preR, int inL, int inR) {if (preL > preR)return;//寻找in[]中的根uint u = inL;while (in[u] != pre[preL]) u++;//左右子树递归访问ToPost(preL + 1, preL + u - inL, inL, u - 1);ToPost(preL + u - inL+1, preR, u + 1, inR);post.push_back(in[u]);
}int main() {//freopen("input.txt", "r", stdin);cin >> N;for (int i = 0; i < N; i++) {cin >> pre[i];}for (int i = 0; i < N; i++)cin >> in[i];ToPost(0, N - 1, 0, N - 1);cout << post[0] << endl;return 0;}

苯办法，先建树

#include<iostream>
#include<vector>
using namespace std;
vector<int> pre, in,post;struct node {int val;struct node *left, *right;
};node* buildTree(int pl, int pr, int il, int ir) {if (pl > pr)return NULL;node *root = new node;root->val = pre[pl];root->left = root->right = NULL;int index = il;while (il <= ir && in[index] != pre[pl])index++;root->left = buildTree(pl+1, index-1-il+pl+1, il, index - 1);root->right = buildTree(pr-(ir-index-1), pr, index + 1, ir);return root;
}void dfs(node *root) {if (root == NULL)return;dfs(root->left);dfs(root->right);post.push_back(root->val);
}int main() {//readint n;cin >> n;pre.resize(n), in.resize(n);for (int i = 0; i < n; ++i)cin >> pre[i];for (int i = 0; i < n; ++i)cin >> in[i];node* root = NULL;root=buildTree(0, n - 1, 0, n - 1);dfs(root);cout << post[0] << endl;system("pause");return 0;
}

参考：