文章

1

粉丝

182

获赞

1

访问

5.5k

头像
无需建树,核心代码 6 行

# include <iostream>
# include <algorithm>
# include <unordered_map>
using namespace std;

string pre, ino;
unordered_map<int, int> mi;
int pos_idx; // 前序遍历目前访问的位置
// [ii, ij]: 中序遍历目前访问的区间
void dfs(int ii, int ij) {
    if (ii > ij) return;
    char val = pre[pos_idx];
    int root_in_ino = mi[val];
    pos_idx ++ ;
    dfs(ii, root_in_ino - 1); // 遍历左子树
    dfs(root_in_ino + 1, ij); // 遍历右子树
    cout << val; // 访问根节点
    return ;
}


int main() {
    cin >> pre >> ino;
    for (int i = 0; i < ino.size(); i ++ ) mi[ino[i]] = i;
    
    dfs(0, ino.size() - 1);
    
    return 0;
} 

 

登录查看完整内容


登录后发布评论

1 条评论
admin SVIP
2022年6月19日 17:07

yes

赞(0)