题目
题目链接
题解
递归。
首先要了解什么是先序遍历,中序遍历和后序遍历。
大佬讲解树的遍历
一般同学们应该都知道如何遍历。
这个题有点像模拟实现题,就是把你手算的过程实现一遍。
整体思路:
先从后序遍历中确定根,再去中序遍历中找到根的左右两侧的子树,再根据中序遍历中确定的左子树,从后序遍历中找到对应的左子树,后序遍历中左子树的根就是左子树序列中的最后一个字母,右子树同左子树。现在我们又得到一个根了,又可以重复上面的过程了。
递归函数我们每次传递中序遍历中此子树的起始索引和终止索引、后序遍历中此子树的起始索引和终止索引、以及这棵子树的结点个数(本质上就是序列的长度)。
递归函数中:
后序遍历的最后一个字母就是这棵子树的根,知道了根的字母,又由于题目说每个结点的字母都不一样,因此我们去遍历中序遍历找到根这个字母所在的索引,以此为分界线,可以将子树划分为子树的左子树和子树的右子树;
知道子树的左右子树(下统称左右子树)分别具有哪些字母了,我们就根据这些字母去后序遍历中确定左右子树。确定的方式也非常简单,我们只要确定出后序遍历中哪一段是左子树,那么剩下一段一定是右子树,因为它们都是连续的一段。我们用两层循环去遍历,外层是中序遍历的左子树字母,内层是后序遍历的字母,只要相等就说明内层遍历到的是左子树的字母,我们就更新一下左子树字母在后序遍历中的最大索引,这样一来从后序遍历序列的头到这个位置都是左子树,而从这个位置一直到尾的前一个都是右子树(尾部是根的字母)。序列长度也很好计算吧。
这样我们就可以继续递归左子树,递归右子树了,边界条件是长度为0,直接返回。
我们其实可以在遇到递归函数中直接输出每次遇到的根,因为是先序遍历嘛,这样完全没问题,而且还不用存下树的结构,很方便。
这个题思路几乎是秒出,但是一点点的小细节把我人卡傻了,split
初始化为l2
在某些情况下陷入死循环,比如代码下面注释的样例。这组样例是我从网上别人的博客里乱翻出来的,一试真死循环了,找了好久才找到这个样例的。太离谱了。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
string s1, s2;
void dfs(int l1, int r1, int l2, int r2, int len) { // s1:中 s2:后
if(len <= 0) return ;
cout << s2[r2]; // 直接输出
int pos = l1, split = l2-1; // pos是中序遍历中根所在索引,split是后序遍历中左子树最右边字母的索引
for(;pos <= r1;pos ++) if(s1[pos] == s2[r2]) break; // 确定pos
for(int i = l1;i < pos;i ++)
for(int j = l2;j < r2;j ++)
if(s1[i] == s2[j]) split = max(split, j); // 确定split
// cout << pos << ' ' << split << endl;
dfs(l1, pos-1, l2, split, pos-l1); // 左子树
dfs(pos+1, r1, split+1, r2-1, r1-pos); // 右子树
}
int main()
{
cin>>s1>>s2;
n = s1.size();
dfs(0, n-1, 0, n-1, n);
return 0;
}
/*
BDCAEHGKF
DCBHKGFEA
ans:ABCDEFGHK
*/