aso优化app推广,点击排名优化,轻量的wordpress,wordpress分享点赞【题目来源】https://www.acwing.com/problem/content/1262/【题目描述】 树的凹入表示法主要用于树的屏幕或打印输出#xff0c;其表示的基本思想是兄弟间等长#xff0c;一个结点的长度要不小于其子结点的长度。 二叉树也可以这样表示#xff0c;假设叶结点的长度为 1其表示的基本思想是兄弟间等长一个结点的长度要不小于其子结点的长度。 二叉树也可以这样表示假设叶结点的长度为 1一个非叶结点的长度等于它的左右子树的长度之和。 一棵二叉树的一个结点用一个字母表示无重复输出时从根结点开始 每行输出若干个结点字符相同字符的个数等于该结点长度 如果该结点有左子树就递归输出左子树 如果该结点有右子树就递归输出右子树。 假定一棵二叉树一个结点用一个字符描述现在给出先序和中序遍历的字符串用树的凹入表示法输出该二叉树。【输入格式】 两行每行是由大写字母组成的字符串一行的每个字符都是唯一的分别表示二叉树的先序遍历和中序遍历的序列。【输出格式】 行数等于该树的结点数每行的字母相同。【数据范围】 输入字符串的长度均不超过26。【输入样例】 ABCDEFG CBDAFEG【输出样例】 AAAA BB C D EE F G【算法分析】 利用下图中的中序、后序遍历示意图计算x、y值的过程可参考确立下文代码中的参数。其中 ile中序遍历左端点位置iri中序遍历右端点位置 ple后序遍历左端点位置pri后序遍历右端点位置 【算法代码】
#include bits/stdc.h
using namespace std;string pre,in;
int a[30];int dfs(int l1, int r1, int l2, int r2) { //preorder inorderif(l1r1) {a[l1]1;return a[l1];}int kin.find(pre[l1]);if(kl2) a[l1]dfs(l11,l1k-l2,l2,k-1);if(kr2) a[l1]dfs(l1k-l21,r1,k1,r2);return a[l1];
}int main() { cinprein;dfs(0,pre.size()-1,0,in.size()-1);for(int i0; ipre.size(); i) {for(int j0; ja[i]; j)coutpre[i];coutendl;}return 0;
}/*
in:
ABCDEFG
CBDAFEGout:
AAAA
BB
C
D
EE
F
G
*/
【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/119108633https://www.acwing.com/solution/content/184637/
