题目描述

树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点的长度要不小于其子结点的长度。
二叉树也可以这样表示，假设叶结点的长度为 1
，一个非叶结点的长度等于它的左右子树的长度之和。
一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始：
每行输出若干个结点字符（相同字符的个数等于该结点长度），
如果该结点有左子树就递归输出左子树；
如果该结点有右子树就递归输出右子树。
假定一棵二叉树一个结点用一个字符描述，现在给出先序和中序遍历的字符串，用树的凹入表示法输出该二叉树。

输入格式

两行，每行是由大写字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的先序遍历和中序遍历的序列。

输出格式

行数等于该树的结点数，每行的字母相同。

数据范围

输入字符串的长度均不超过26。

输入样例：

ABCDEFG
CBDAFEG

输出样例：

AAAA
BB
C
D
EE
F
G

#include<iostream>

using namespace std;

/*
凹入表示法：
1.首先需要知道每个结点的长度，结点长度的计算分为叶子结点和非叶子结点，其中叶子结点的长度为1，而非叶子结点的长度等于它左右子树的长度之和；
2.然后按照先序遍历的顺序每行输出，每个结点输出的个数取决于该结点的长度。
*/

string pre,in;
int a[30];//每个节点凹入表示法的长度

int dfs(int l1, int r1, int l2, int r2)// 先序 and 中序 
{
    if(l1 == r1)
    {
        a[l1] = 1;
        return a[l1];
    }

    int k = in.find(pre[l1]);

    if(k > l2) a[l1] += dfs(l1 + 1, l1 + k - l2, l2, k - 1);//左子树
    if(k < r2) a[l1] += dfs(l1 + k - l2 + 1, r1, k + 1, r2);//右子树

    return a[l1]; 
}

int main()
{
    cin>>pre>>in;
    dfs(0,pre.size()-1,0,in.size()-1);
    for(int i = 0; i<pre.size(); i++)
    {
        for(int j = 0; j<a[i]; j++)
            cout<<pre[i];
        cout<<endl;
    }
    return 0;
}