html网站首页图片切换,网店装修店面,vps做网站需要做哪些准备,外贸商城网站模板一#xff1a;题目#xff1a;
给定一棵二叉树的先序遍历序列和中序遍历序列#xff0c;要求计算该二叉树的高度。
输入格式: 输入首先给出正整数N#xff08;≤50#xff09;#xff0c;为树中结点总数。下面两行先后给出先序和中序遍历序列#xff0c;均是长度为N的…一题目
给定一棵二叉树的先序遍历序列和中序遍历序列要求计算该二叉树的高度。
输入格式: 输入首先给出正整数N≤50为树中结点总数。下面两行先后给出先序和中序遍历序列均是长度为N的不包含重复英文字母区别大小写的字符串。
输出格式: 输出为一个整数即该二叉树的高度。
输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5
二思路
利用前序和中序进行建树然后求取二叉树的高度
三上马
/*
思路根据中序和前序进行建树 然后求的树的高度
*/
#includebits/stdc.h
using namespace std;typedef struct TNode* Bintree;
typedef struct TNode{char Date;Bintree left,right;
}tnode;Bintree CreatBintree(string s1,string s2,int prel,int prer,int inl,int inr)
{if(prel prer){return NULL;}Bintree BT (Bintree)malloc(sizeof(struct TNode));BT-Date s1[prel];BT-left NULL;BT-right NULL;// cout s1[prel];int temp; for( int i inl; i inr; i ){if( s2[i] s1[prel]){temp i;break;}}int numleft temp - inl;//求出左子树上的结点数目BT-left CreatBintree(s1,s2,prel1,prel numleft,inl,temp-1);BT-right CreatBintree(s1,s2,prelnumleft 1,prer,temp1,inr);return BT;}int treehight(Bintree Bt)
{if(Bt NULL)return 0;int m,n;m treehight(Bt-left) 1;n treehight(Bt-right) 1;return m n? m:n;
}int main(){int N;string str1,str2;cin N str1 str2;Bintree Bt CreatBintree(str1,str2,0,N-1,0,N-1);//houxv(Bt);int cnt treehight(Bt);cout cnt;} 总结
这种题做了三遍了核心递归建树那部分真的难 参数稍微错一点 就会 出现访问越界问题 用本题给的示例进行找规律 不好最好自己找一个左右子树结点个数差不多的二叉树 来找规律我是拿笔在纸上自己递归几遍 就这样一点点找规律。 加油陌生的你
