蓝桥杯算法训练VIP-求先序排列

题目

题目链接

题解

递归。

首先要了解什么是先序遍历，中序遍历和后序遍历。 大佬讲解树的遍历

一般同学们应该都知道如何遍历。 这个题有点像模拟实现题，就是把你手算的过程实现一遍。

整体思路： 先从后序遍历中确定根，再去中序遍历中找到根的左右两侧的子树，再根据中序遍历中确定的左子树，从后序遍历中找到对应的左子树，后序遍历中左子树的根就是左子树序列中的最后一个字母，右子树同左子树。现在我们又得到一个根了，又可以重复上面的过程了。

递归函数我们每次传递中序遍历中此子树的起始索引和终止索引、后序遍历中此子树的起始索引和终止索引、以及这棵子树的结点个数（本质上就是序列的长度）。 递归函数中： 后序遍历的最后一个字母就是这棵子树的根，知道了根的字母，又由于题目说每个结点的字母都不一样，因此我们去遍历中序遍历找到根这个字母所在的索引，以此为分界线，可以将子树划分为子树的左子树和子树的右子树； 知道子树的左右子树（下统称左右子树）分别具有哪些字母了，我们就根据这些字母去后序遍历中确定左右子树。确定的方式也非常简单，我们只要确定出后序遍历中哪一段是左子树，那么剩下一段一定是右子树，因为它们都是连续的一段。我们用两层循环去遍历，外层是中序遍历的左子树字母，内层是后序遍历的字母，只要相等就说明内层遍历到的是左子树的字母，我们就更新一下左子树字母在后序遍历中的最大索引，这样一来从后序遍历序列的头到这个位置都是左子树，而从这个位置一直到尾的前一个都是右子树（尾部是根的字母）。序列长度也很好计算吧。 这样我们就可以继续递归左子树，递归右子树了，边界条件是长度为0，直接返回。 我们其实可以在遇到递归函数中直接输出每次遇到的根，因为是先序遍历嘛，这样完全没问题，而且还不用存下树的结构，很方便。

这个题思路几乎是秒出，但是一点点的小细节把我人卡傻了，split初始化为l2在某些情况下陷入死循环，比如代码下面注释的样例。这组样例是我从网上别人的博客里乱翻出来的，一试真死循环了，找了好久才找到这个样例的。太离谱了。

代码

#include
using namespace std;

int n;
string s1, s2;

void dfs(int l1, int r1, int l2, int r2, int len) { // s1：中    s2：后 
	if(len