Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》

欢迎点赞，关注！

1、求解先序排列 

题解：

      题目给了中序和后序排列，让我们求先序。

      首先根据后序，我们能确定根，也就是后序德最后一个字母

      再从中序中找到根节点，这样，根节点之前的就是左子树，后面的就是右子树。我们再把左右子树对应的中序，后序排列传进函数，运用递归求解出先序排列。

#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
string m;
string e;//存中序和后序排列
void dfs(int l1, int r1, int l2,int r2)
{if (r1 < l1 ||r2<l2){return ;}//当左右子树不合法时退出递归char ch = e[r2];cout << ch;int p=0;while (m[p] != ch){p++;}//p指向根的位置//把左右子树的中序和后序对应传入dfs进行递归int d = p - l1;//子树长度//注意区分l和1.d等于p减去第一个下标l,也就是0dfs(l1, p - 1,l2,l2+d-1);dfs(p + 1, r1, l2 + d, r2 - 1);
}
int main()
{cin >> m;cin >> e;int l1 = 0;//中序排序的第一个节点int r1 = m.size() - 1;//中序排序的最后一个节点int l2 = 0;//后序排序的第一个节点int r2 = e.size() - 1;//后序排序的最后一个节点//注意传入的第一个节点的下标是0dfs(l1,r1,l2,r2);return 0;
}

2、美国血统

题解：

      这个题和上面的几乎一样。

#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
string m;
string e;
void dfs(int l1, int r1, int l2,int r2)
{if (r1 < l1 || r2 < l2){return;}char ch = e[l2];//根int p=0;while (m[p] != ch) p++;int d = p - l1;dfs(l1, p-1, l2+1, l2 + d);dfs(p+1, r1, l2 + d + 1, r2);//左右子树对应的前序和中序cout << ch;
}
int main()
{//美国血统//给定中序和前序求解后序cin >> m >> e;int l1 = 0;int r1 = m.size() - 1;int l2 = 0;int r2 = e.size() - 1;//对应的中序和前序的首末节点（字符）dfs(l1, r1, l2, r2);return 0;
}

       好了，今天的内容就分享到这，我们下期再见！