一些关于树的部分的一些题目。
L2-004 这是二叉搜索树吗？ (25 分)
描述：
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
- 其左子树中所有结点的键值小于该结点的键值；
- 其右子树中所有结点的键值大于等于该结点的键值；
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。
输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。
输入样例 1：
输出样例 1：
输入样例 2：
输出样例 2：
输入样例 3：
输出样例 3：
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include<bits/stdc++.h>
using namespace std;
int input[10000],output[10000];
int count1=0;
int Tree1(int left,int right)
{
if(left > right )
return 1;
int root = input[left];
int i=left+1;
for(;input[i]<root&&i<=right ;)
{
i++;
}
for(int j=i ; j <=right ;j++)
{
if(input[j]<root)
return 0;
}
if(Tree1(left+1,i-1)==0)
return 0;
if(Tree1(i,right)==0)
return 0;
output[count1++] = root;
return 1;
}
int Tree2(int left,int right)
{
if(left > right )
return 1;
int root = input[left];
int i=left+1;
for(;input[i]>=root&&i<=right;)
{
i++;
}
for(int j=i;j<right;j++)
{
if(input[j]>=root)
{
return 0;
}
}
if(Tree2(left+1,i-1)==0)
return 0;
if(Tree2(i,right)==0)
return 0;
output[count1++] = root;
return 1;
}
int main()
{
int n=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&input[i]);
}
if(n==1)
{
printf("YES\n%d\n", input[0]);
return 0;
}
if(input[0]>input[1])
{
if(Tree1(0,n-1)==0)
{
printf("NO\n");
}
else
{
printf("YES\n");
for(int i=0;i<n-1;i++)
{
printf("%d ",output[i]);
}
printf("%d",output[n-1]);
}
}
else
{
if(Tree2(0,n-1) == 0)
{
printf("NO\n");
}
else
{
printf("YES\n");
for(int i=0;i<n-1;i++)
{
printf("%d ",output[i]);
}
printf("%d",output[n-1]);
}
}
return 0;
}
|
L2-006 树的遍历 (25 分)
描述：
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
1
2
3
| 7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
|
输出样例：
code：
失败代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| 刚开始的代码，先记录一下。
#include<bits/stdc++.h>
using namespace std;
int input1[40],input2[40];
int output[40];
int countN = 0 ;
int createT(int left1 ,int right1 , int left2 ,int right2)
{
if(left1>right1)
{
return -1;
}
int root =input1[right1];
int i=0,j=0;
int tmp=0;
for(i=left2;i<=right2;i++,tmp++)
{
if(input2[i]==root)
{
tmp=i;
break;
}
}
printf("%d ",tmp);
int increace =tmp;
output[countN++] = root;
output[countN++] = createT(left1,left1+increace-1,left2,tmp-1);
output[countN++] = createT(left1+increace,right1,tmp+1,right2);
return root;
}
int main()
{
int n=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&input1[i]);
}
for(int i=0;i<n;i++)
{
scanf("%d",&input2[i]);
}
if(createT(0,n-1,0,n-1)==0)
printf("No");
else
printf("Yes");
for(int i=0;i<n - 1;i++)
{
printf("%d ",output[i] );
}
printf("%d",output[n-1]);
return 0;
}
|
代码：
结束符