7-1 根据后序序列和中序序列确定二叉树
二叉树采用二叉链表存储,要求根据给定的后序遍历序列和中序遍历序列建立二叉树,并输出二叉树的深度及其先序遍历序列。
输入格式:
测试数据有多组,处理到文件尾。每组测试数据的第一行输入结点数n(1≤n≤10),第二、三行各输入n个整数,分别表示二叉树的后序遍历序列和中序遍历序列。
输出格式:
对于每组测试,在一行上分别输出该二叉树的深度及其先序遍历序列。每两个数据之间留一个空格。
输入样例:
9
7 4 2 8 9 5 6 3 1
4 7 2 1 8 5 9 3 6
输出样例:
4 1 2 4 7 3 5 8 9 6
我的代码:
#include<bits/stdc++.h>
using namespace std;
typedef struct bitnode{
int data;
bitnode* lc;
bitnode* rc;
}bitnode,*bitree;
void pre(bitnode *tree)
{
if (tree == NULL)
{
return;
}
cout<<" " << tree->data;
pre(tree->lc);
pre(tree->rc);
}
void create(int post[], int mid[], int n,bitree &tree) {
if (n <= 0)
return;
tree = (bitree)malloc(sizeof(bitnode));
int r = post[n - 1];
tree->data = r;
int k;
for (k = 0;k < n;k++)
if (mid[k] == r)
break;
create(post, mid, k,tree->lc);
create(post + k, mid + k + 1, n - k - 1,tree->rc);
}
int Depth(bitree Tree)
{
int m, n;
if (Tree == NULL) return 0;
m = Depth(Tree->lc);
n = Depth(Tree->rc);
if (m > n) {
return m+1 ;
}
else {
return n+1 ;
}
}
int main() {
int n;
int post[20], mid[20];
bitree tree;
cin >> n;
for (int i = 0;i < n;i++)
cin >> post[i];
for (int i = 0;i < n;i++)
cin >> mid[i];
create(post, mid, n, tree);
cout << Depth(tree);
pre(tree);
return 0;
}
/*
9
7 4 2 8 9 5 6 3 1
4 7 2 1 8 5 9 3 6
*/
测试用例运行结果是正确的,但提交答案显示答案错误,请问问题在哪里?