7-23 还原二叉树（25 分)

比眉伴天荒 2022-02-27 14:28 180阅读 0赞

7-23 还原二叉树 （25 分)

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

### 输入格式: ###

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

### 输出格式: ###

输出为一个整数，即该二叉树的高度。

### 输入样例: ###

9
    ABDFGHIEC
    FDHGIBEAC

### 输出样例: ###

5

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int pre[505],in[505],l[505],r[505];
    int maxx;
    int dfs(int l1,int r1,int l2,int r2)
    {
    	if(l1>r1)return -1;
    	int root=pre[l1];
    	int p=l2;
    	while(root!=in[p])p++;
    	int cnt=p-l2;
    	l[root]=dfs(l1+1,l1+cnt,l2,p-1);
    	r[root]=dfs(l1+cnt+1,r1,p+1,r2);
    	return root;
    }
    void sc(int x,int s)
    {
    	if(l[x]==-1&&r[x]==-1)
    	{
    		if(s>maxx)
    		maxx=s;
    		return;
    	}
    	if(l[x]!=-1)sc(l[x],s+1);
    	if(r[x]!=-1)sc(r[x],s+1);
    }
    int main()
    {
    	int n,i,j;
    	char p[55],inn[55];
    	memset(l,-1,sizeof l);
    	memset(r,-1,sizeof r);
    	scanf("%d",&n);
    	scanf("%s",p);
    	scanf("%s",inn);
    	for(i=0;i<n;i++)
    	{
    		pre[i]=p[i]-'A';
    		in[i]=inn[i]-'A';
    	}
    	maxx=-1;
    	dfs(0,n-1,0,n-1);
    	sc(pre[0],1);
    	printf("%d\n",maxx);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 PTA 是否二叉搜索树 (25分)

PTA 是否二叉搜索树 (25分) 本题要求实现函数，判断给定二叉树是否二叉搜索树。函数接口定义： bool IsBST ( BinTree T );

╰半夏微凉°/ 2023年07月26日 05:26/ 0 赞/ 17 阅读

相关 6-2 二叉树的遍历 (25分)

本题要求给定二叉树的4种遍历。函数接口定义： void InorderTraversal( BinTree BT ); void PreorderTr

客官°小女子只卖身不卖艺/ 2023年07月18日 02:16/ 0 赞/ 17 阅读

相关数据结构实验之二叉树四：还原二叉树

[sdut原题链接][sdut] 数据结构实验之二叉树四：还原二叉树 Time Limit: 1000MS Memory Limit: 65536KB Problem

阳光穿透心脏的1/2处/ 2022年07月12日 02:38/ 0 赞/ 209 阅读

相关 L2-011 玩转二叉树（25 分）

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

旧城等待，/ 2022年05月24日 02:47/ 0 赞/ 177 阅读

相关 6-2 二叉树的遍历（25 分）

本题要求给定二叉树的4种遍历。函数接口定义： void InorderTraversal( BinTree BT ); void PreorderTr

╰半夏微凉°/ 2022年04月22日 03:30/ 0 赞/ 185 阅读

相关还原二叉树

给定一棵二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列

布满荆棘的人生/ 2022年04月22日 03:16/ 0 赞/ 168 阅读

相关 7-23 还原二叉树（25 分）

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均

桃扇骨/ 2022年04月22日 03:12/ 0 赞/ 211 阅读

相关 7-23 还原二叉树（25 分)

7-23 还原二叉树（25 分) 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。

比眉伴天荒/ 2022年02月27日 14:28/ 0 赞/ 181 阅读

相关还原二叉树PTA

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均

男娘i/ 2022年02月04日 13:43/ 0 赞/ 259 阅读

相关还原二叉树

还原二叉树 -------------------- 想要还原一棵二叉树，需要知道两种序列先序和中序或后序和中序 --------------------

待我称王封你为后i/ 2022年02月01日 10:53/ 0 赞/ 227 阅读