46 lines
1.1 KiB
C++
46 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
string post_str; //后序
|
||
string in_str; //中序
|
||
|
||
//后序的最后一个是根,先序是先输出数的根 那就找一次输出一次,然后继续找出左树和右树,直到空树时停止。
|
||
//后序遍历的范围 l1-r1
|
||
//中序遍历的范围 l2-r2
|
||
void dfs(int l1, int r1, int l2, int r2) {
|
||
//当前为空树 则直接返回,递归终止条件
|
||
if (l1 > r1 || l2 > r2) return;
|
||
|
||
//从中序遍历中找出左树的范围
|
||
int i = in_str.find(post_str[r1]);//post_str[r1]是指尾巴是根结点
|
||
|
||
//左子树节点有多少个
|
||
int cnt = i - l2;
|
||
|
||
//后序遍历的最后一个一定是节点的根，输出根的值
|
||
cout << post_str[r1];
|
||
|
||
// 递归构建左树
|
||
// 后序,中序
|
||
dfs(l1, l1 + cnt - 1, l2, i - 1);
|
||
// 递归构建右树
|
||
// 后序,中序
|
||
dfs(l1 + cnt, r1 - 1, i + 1, r2);
|
||
}
|
||
|
||
/**
|
||
BADC 中序
|
||
BDCA 后序
|
||
|
||
BADC
|
||
BDCA
|
||
|
||
参考答案：ABCD
|
||
*/
|
||
int main() {
|
||
cin >> in_str >> post_str;
|
||
int right = in_str.size() - 1; //right索引：因为是0开始，所以要-1
|
||
dfs(0, right, 0, right);
|
||
return 0;
|
||
} |