<笔记>快速排序的切分

#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 30;
unordered_map<char, int> pos, l, r // pos记录中序遍历所在元素的位置;
string pre, in;
string post;
void dfs(char root){
    if(l.count(root)) dfs(l[root]);
    if(r.count(root)) dfs(r[root]);
    post += root;
}

char dfs(int il, int ir, int pl, int pr){
    char root = pre[pl];
    int k = pos[root];
    if(k > il) l[root] = dfs(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
    if(k < ir) r[root] = dfs(k + 1, ir, pl + 1 + k - il, pr);
    return root;
}

int main(){
    while(cin>> pre >> in){
        pos.clear(), l.clear(), r.clear();
        int n = pre.size();
        for(int i = 0; i < in.size(); i ++ ) pos[in[i]] = i;
        char root = dfs(0, n - 1, 0, n - 1);
        post.clear();
        dfs(root);
        cout << post << endl;
    }
}