思路

先序中序重建后节点输出次数为子树叶子数，单孩子链长度仍为1，区别树深度。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
string pre,in;int pos=0;struct Node{char c;int l=-1,r=-1,leaves=0;Node(char x):c(x){} };vector<Node>t;int make(int l,int h){if(l>=h)return -1;char c=pre[pos++];int p=in.find(c),id=t.size();t.push_back(Node(c));int a=make(l,p),b=make(p+1,h);t[id].l=a;t[id].r=b;t[id].leaves=(a<0&&b<0)?1:(a<0?0:t[a].leaves)+(b<0?0:t[b].leaves);return id;}void emit(int v){if(v<0)return;cout<<string(t[v].leaves,t[v].c)<<'\n';emit(t[v].l);emit(t[v].r);}int main(){cin>>pre>>in;emit(make(0,in.size()));}