AcWing 1259. 二叉树遍历
原题链接
中等
作者:
fwb
,
2024-07-26 23:43:16
,
所有人可见
,
阅读 2
//acwing 1259. 二叉树遍历
//假定一棵二叉树一个结点用一个字符描述,
//现在给出中序和按层遍历的字符串,求该树的先序遍历字符串。
//不知道这个方法是否具有通用性,
//我自己在纸上画了画 中+前 中+后的组合,
//貌似 中+前(可能可以,具体也没有进行实现)依旧可以用这个,中加后不会
//另外,改变 cout << ceng[i]; 位置即可改变输出顺序为: 前/中/后
#include<iostream>
using namespace std;
string zhong, ceng;
void dfs(int L1, int R1, int L2, int R2) {
int i, j;
bool flag = false;
for (i = L1; i <= R1; i++) {
for (j = L2; j <= R2; j++) {
if (ceng[i] == zhong[j]) { flag = true; break; }
}
if (flag == true)break;
}
cout << ceng[i];
if (j > L2) { dfs(L1 + 1, R1, L2, j - 1); }
if (j < R2) { dfs(L1 + 1, R1, j + 1, R2); }
}
int main()
{
cin >> zhong >> ceng;
dfs(0, ceng.size()-1, 0, zhong.size()-1);
return 0;
}