题解 | 求先序排列-NOIP2001普及组复赛C题
C-求先序排列_NOIP2001普及组复赛
https://ac.nowcoder.com/acm/contest/229/C
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度 ≤ 8）。
输入描述:
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出描述:
1行，表示一棵二叉树的先序。
示例1
输入
BADC
BDCA
输出
ABCD
解答
思路：
树的遍历方式：
树的遍历方式：
先序遍历：先根节点后左右子树。
中序遍历：先左子树，再根节点，最后右子树。
后序遍历：先左右子树后根节点。
后序遍历：先左右子树后根节点。
步骤：
先找到根节点并输出，即后序遍历的最后一点。
将中序遍历和后序遍历后的序列各分为两棵子树。
递归，重复一，二步骤，直到中序遍历后的长度小于等于0。
先找到根节点并输出，即后序遍历的最后一点。
将中序遍历和后序遍历后的序列各分为两棵子树。
递归，重复一，二步骤，直到中序遍历后的长度小于等于0。
代码如下：
来源：RollerCompaction
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void tree(string s1,string s2){
int len1=s1.size();
int len2=s2.size();
if(len1>0){
char ch=s2[len2-1]; //根节点
cout<<ch; //每次递归输出根节点
int pos=s1.find(ch); //在s1中找到ch出现的位置
tree(s1.substr(0,pos),s2.substr(0,pos)); //递归左子树
tree(s1.substr(pos+1),s2.substr(pos,len1-pos-1)); //递归右子树
}
}
int main() {
string str1,str2;
cin>>str1>>str2;
tree(str1,str2); //构建左子树
return 0;
} 来源：RollerCompaction
投递4399游戏等公司10个岗位 >
学而思公司福利 378人发布