便捷的网站建设,北京最大的互联网公司,网站策划模板,网站内容管理规范先序中序还原二叉树
题目描述 给定一棵二叉树的先序遍历序列和中序遍历序列#xff0c;要求计算该二叉树的高度。
输入 输入首先给出正整数N#xff08;≤50#xff09;#xff0c;为树中结点总数。下面两行先后给出先序和中序遍历序列#xff0c;均是长度为N的不包含重…先序中序还原二叉树
题目描述 给定一棵二叉树的先序遍历序列和中序遍历序列要求计算该二叉树的高度。
输入 输入首先给出正整数N≤50为树中结点总数。下面两行先后给出先序和中序遍历序列均是长度为N的不包含重复英文字母区别大小写的字符串。
输出 输出为一个整数即该二叉树的高度。
输入样例1 9 ABDFGHIEC FDHGIBEAC
输出样例1 5
#includebits/stdc.h
using namespace std;
int high0;
struct trees
{char value;trees* leftNULL;trees* rightNULL;
};
trees* setTree(int pl,int pr,int ml,int mr,mapchar,int m,string prior,string middle,int height)
{//根节点char rootprior[pl];//根节点在中序遍历序列的位置int middleIndexm[root];trees* tree new trees;tree-valueroot;if(middleIndexml) tree-leftsetTree(pl1,plmiddleIndex-ml,ml,middleIndex-1,m,prior,middle,height1);if(middleIndexmr) tree-rightsetTree(plmiddleIndex-ml1,pr,middleIndex1,mr,m,prior,middle,height1);highmax(high,height);return tree;
}
int main()
{int n;cinn;//记录字符在中序遍历序列位置mapchar,int m;string prior,middle;cinpriormiddle;for(int i0;imiddle.size();i) m[middle[i]]i;trees* tnew trees;//建树tsetTree(0,n-1,0,n-1,m,prior,middle,1);couthighendl;return 0;
}
