【二叉树】求先序排列
2024-10-27 11:57:21
发布于：北京
1阅读
0回复
0点赞
题目描述
给出一棵二叉树的中序与后序排列。求出它的前序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。
输入格式
共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式
共一行一个字符串，表示一棵二叉树的前序。
样例组输入#1
BADC
BDCA
样例组输出#1
ABCD
#include <bits/stdc++.h>
using namespace std;
string ss1,ss2;
//s1是中序,s2是后序
void dfs1(string s1,string s2){
//指定边界
if(s1.size() == 0) return 0;
//获取后序的最后一个字母s2[s2.size() - 1]作为根节点
int id = find(s2[s2.size() - 1]); //储存 根节点在中序遍历时的位置
//输出根节点
cout << s1[id];
//字串：原字符串.substr(a,b) a代表开头位置的索引，b代表字串的长度
//s1[左子树]id[右子树]-----左子树的起点是：0，长度：id；右子树：起点：id + 1，长度： s1.size() - id - 1
//s2[左子树][右子树]id-----左子树的起点是：0，长度：id；右子树：起点：id，长度： s1.size() - id - 1
//递归处理左子数
dfs1(s1.substr(0,id),s2.substr(0,id));
//递归处理右子树
dfs1(s1.substr(id + 1,s1.size() - id - 1),s2.substr(id,s1.size() - id - 1));
}
int main(){
cin >> ss1 >> ss2;
dfs1(ss1,ss2);
return 0;
}
这里空空如也
有帮助，赞一个