先序+中序还原二叉树【数据结构】
先序+中序还原二叉树
题目描述
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入
输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。
输出
输出为一个整数，即该二叉树的高度。
输入样例1
9
ABDFGHIEC
FDHGIBEAC
输出样例1
5
#include<bits/stdc++.h>
using namespace std;
int high=0;
struct trees
{char value;trees* left=NULL;trees* right=NULL;
};
trees* setTree(int pl,int pr,int ml,int mr,map<char,int> &m,string prior,string middle,int height)
{//根节点char root=prior[pl];//根节点在中序遍历序列的位置int middleIndex=m[root];trees* tree = new trees;tree->value=root;if(middleIndex>ml) tree->left=setTree(pl+1,pl+middleIndex-ml,ml,middleIndex-1,m,prior,middle,height+1);if(middleIndex<mr) tree->right=setTree(pl+middleIndex-ml+1,pr,middleIndex+1,mr,m,prior,middle,height+1);high=max(high,height);return tree;
}
int main()
{int n;cin>>n;//记录字符在中序遍历序列位置map<char,int> m;string prior,middle;cin>>prior>>middle;for(int i=0;i<middle.size();i++) m[middle[i]]=i;trees* t=new trees;//建树t=setTree(0,n-1,0,n-1,m,prior,middle,1);cout<<high<<endl;return 0;
}