题目链接

[NOIP2001]求先序排列https://ac.nowcoder.com/acm/contest/21763/1011

思路

通过先序和中序求后序，与通过后序和中序求先序的方法几乎是一样的思路，只是需要留意先序的遍历顺序是根左右，后序的遍历顺序是左右根即可。
这里我们以后序和中序构建先序为例子来讲讲如何实现。

首先要搞清楚中序遍历和后序遍历的关系。
给出中序遍历序列BADC和后序遍历序列BDCA，我们来看看处理的步骤。\

1. 记每棵子树（包括待求解树本身）中序遍历中元素位置为[l1, r1]，在后序遍历中元素位置为[l2, r2]，显然有。通过调用solve(0, inorder.size()-1, 0, inorder.size()-1)进入第一次根结点处理。其中参数列表solve(int l1, int r1, int l2, int r2)
2. 根据后序遍历的顺序为左右根可以得出当前后序遍历的最后一位一定是树的根结点（这里的当前不仅仅指的是整棵树的后序遍历，每次划分左右子树区间后同样最后一位是子树的根结点）。即当前根结点为A
3. 在中序遍历中找到根结点(当前为A)对应的下标pos，此时pos=1
4. 根据中序遍历顺序为左根右，我们可以知道A左侧的所有元素都是在A的左子树上，同理A右侧的所有元素都是在A的右子树上。可以推出A的左子树在中序遍历中元素位置为[l1, pos-1]，左子树在后序遍历中元素位置为[l2, l2+pos-1-l1]，同理可以推出右子树的元素位置，在此不多赘述。
5. 找到左子树和右子树的位置之后我们即可通过同样的方式对子树操作，把子树看作是步骤1输入的树，分别处理左右子树逻辑。
6. 递归完成上述步骤。

不建树代码

不难发现其实在生成根结点->处理左子树->处理右子树的这个过程中就是一个先序遍历的顺序，那么可以在处理过程中直接输出每次生成的根结点的值，这本身就是先序遍历序列。

#include <bits/stdc++.h>
#define int long long

using namespace std;

unordered_map<char, int> mp; // map用来直接存储当前结点在中序遍历中的下标，可以在O(1)的时间查询

string inorder, postorder;

void solve(int l1, int r1, int l2, int r2){
    if (l1 > r1) return;
    char root = postorder[r2];
    cout << root;
    int pos = mp[root];
    solve(l1, pos - 1, l2, l2 + (pos - l1) - 1);
    solve(pos + 1, r1, r2 - r1 + pos, r2 - 1);
}

signed main(){
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> inorder >> postorder;
    for (int i = 0; i < inorder.size(); i++){
        mp[inorder[i]] = i;
    }
    int len = inorder.size();
    solve(0, len - 1, 0, len - 1);
    
    return 0;
}

建树代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

class treeNode{
public:
	int val;
  	treeNode* left;
  	treeNode* right;
  	treeNode(int val){
    	this->val = val;
    	this->left = nullptr;
      	this->right = nullptr;
    }
}* Tree;

unordered_map<char, int> mp;

string inorder, postorder;

Tree solve(int l1, int r1, int l2, int r2){
    if (l1 > r1) return nullptr;
    char root_val = postorder[r2];
  	treeNode * root = new treeNode(root_val);
    int pos = mp[root];
    root->left = solve(l1, pos - 1, l2, l2 + (pos - l1) - 1);
    root->right = solve(pos + 1, r1, r2 - r1 + pos, r2 - 1);
  	return root;
}

signed main(){
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> inorder >> postorder;
    for (int i = 0; i < inorder.size(); i++){
        mp[inorder[i]] = i;
    }
    int len = inorder.size();
    Tree root = solve(0, len - 1, 0, len - 1);
    
    return 0;
}