题目描述

现给定一棵二叉树的先序遍历序列和中序遍历序列，计算该二叉树的高度。

输入

输入包含多组测试数据，每组输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出

对于每组输入，输出一个整数，即该二叉树的高度。

样例输入

9
ABDFGHIEC
FDHGIBEAC
7
Abcdefg
gfedcbA

样例输出

5
7

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50;
struct node{
	int data;
	node *lchild;
	node *rchild;
};
char pre[maxn],in[maxn];
//已知先序序列和中序序列，构建二叉树 
node *create(int preL,int preR,int inL,int inR)
{
    if(preL>preR) return NULL;
	node *root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
    	if(in[k]==pre[preL]){
    		break;
		}
	}
	int numLeft=k-inL;
	root->lchild=create(preL+1,preL+numLeft,inL,k-1);
	root->rchild=create(preL+numLeft+1,preR,k+1,inR);
    return root;
}
//求深度
int DepthOfTree(node* root)
{
    if(root)
        return DepthOfTree(root->lchild)>DepthOfTree(root->rchild)?DepthOfTree(root->lchild)+1:DepthOfTree(root->rchild)+1;
    if( root == NULL )
        return 0;
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>pre[i];
	}
	for(int i=0;i<n;i++){
		cin>>in[i];
	}
	node *root=create(0,n-1,0,n-1);
	cout<<DepthOfTree(root);
}

若已知序序列和后序序列，构建二叉树可用以下代码代替

//已知中序序列和后序序列，构建二叉树 
node *create(int postL,int postR,int inL,int inR)
{
    if(postL>postR) return NULL;
	node *root=new node;
    root->data=post[postR];
    int k;
    for(k=inL;k<=inR;k++){
    	if(in[k]==post[postR]){
    		break;
		}
	}
	int numLeft=k-inL;
	root->lchild=create(postL,postL+numLeft-1,inL,k-1);
	root->rchild=create(postL+numLeft,postR-1,k+1,inR);
    return root;
}

关于二叉树的其他基本操作，在这里二叉树的建立与遍历详解讲述的很清晰，读者可以自行参阅。