测试地址：☞
【题目描述】
树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点的长度要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1，一个非叶结点的长度等于它的左右子树的长度之和。
一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始：
每行输出若干个结点字符（相同字符的个数等于该结点长度），
如果该结点有左子树就递归输出左子树；
如果该结点有右子树就递归输出右子树。
假定一棵二叉树一个结点用一个字符描述，现在给出先序和中序遍历的字符串，用树的凹入表示法输出该二叉树。
【输入】
两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的先序遍历和中序遍历的序列。
【输出】
行数等于该树的结点数，每行的字母相同。
【输入样例】
ABCDEFG CBDAFEG【输出样例】
AAAA BB C D EE F G【AC代码】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100010; char a[maxn], b[maxn]; int c[maxn], la, lb; // c数组为结点长度 int f(int l1, int r1, int l2, int r2){ if(l1 == r1){ c[l1] = 1; return c[l1]; } int i; for(i = l2; i <= r2; i++) if(a[l1] == b[i]) //找根节点 break; if(i < r2) c[l1] += f(r1-(r2-(i+1)), r1, i+1, r2); if(i > l2) c[l1] += f(l1+1, l1+i-l2, l2, i-1); return c[l1]; } int main(){ cin >> a >> b; la = strlen(a); lb = strlen(b); f(0, la-1, 0, lb-1); for(int i = 0; i < la; i++){ for(int j = 1; j <= c[i]; j++) printf("%c", a[i]); printf("\n"); } return 0; }
