7-4 是否同一棵二叉搜索树

题目描述

判断给定的插入序列是否构成同一棵二叉搜索树

(二叉搜索树:所有左子树元素都小于自身,所有右子树元素都大于自身)

输入

1
2
3
4
5
6
7
8
9
8
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出

1
2
3
Yes
No
No

思路

判断数列的奇淫技巧,测试点1过不了。

哈哈现在我的奇淫技巧过了。

更新了根据即将插入的根进行判断。

难点

选择比较的方法以及原始数据和比较数据的储存形式

体会与感想

自己写的代码多看几遍总归是能看懂的,理清楚的。

还有很想说的是cmake不支持中文以及文件名中的空格,以后再也不用中文了。

真的,实在是..所有中文一律乱码

看了视频之后再写真的是畅通无比,一次提交直接AC。

膜递归…

源代码

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
#include <iostream>

using namespace std;

void comparetree(int n, int l);

int main(int argc, char const *argv[]) {
freopen("D:\\SJTU\\Freshman Summer\\DS\\test.txt", "r", stdin);
while (true) {
int n;cin>>n;
if (n==0) break;
int l;cin>>l;
comparetree(n,l);
}
return 0;
}

void print(bool same)
{
switch (same) {
case true: cout << "Yes" << endl;break;
case false:cout << "No" << endl;break;
}
}

void comparetree(int n, int l)
{
int * src = new int [n]; //src--the original array
int * select = new int [n]; //select 0-->not added to the cmp tree
for (size_t i = 0; i < n; i++) cin >> src[i]; //select 1-->added to the cmp tree
int * cmp = new int [n];
for (size_t i = 0; i < l; i++) {
bool same = true;
for (size_t i = 0; i < n; i++) {cin >> cmp[i];select[i]=0;}
if (src[0]!=cmp[0]) { //judge the head
same = false;
print(same);
continue;
}else select[0] = 1;
for (size_t i = 1; i < n && same; i++) { //i--indecate the cmp node
int rootcmp = src[0];
for (size_t k = 1; k < n; k++) {
if (src[k]>rootcmp&&select[k]==1&&cmp[i]>rootcmp) {
rootcmp = src[k];
}else if (src[k]<rootcmp&&select[k]==1&&cmp[i]<rootcmp) {
rootcmp = src[k];
}
}
for (size_t j = 1; j < n; j++) {
if (select[j]==1) continue;
if (cmp[i]==src[j]) {
select[j] = 1;
break;
}
int rootsrc = src[0];
for (size_t k = 1; k < j; k++) {
if (src[k]>rootsrc&&src[j]>rootsrc) {
rootsrc = src[k];
}else if (src[k]<rootsrc&&src[j]<rootsrc) {
rootsrc = src[k];
}
}
if (rootcmp==rootsrc) {
if (cmp[i]>rootcmp&&src[j]>rootsrc&&cmp[i]!=src[j]) {
same = false;
print(same);
break;
}
if (cmp[i]<rootcmp&&src[j]<rootsrc&&cmp[i]!=src[j]) {
same = false;
print(same);
break;
}
}
}
}
if (same) print(same);
}
}

顺便再贴一下看了视频之后的源码
结构更加清晰

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
#include <iostream>

using namespace std;

struct node {
int value;
node * left;
node * right;
int select;
};

node * maketree(int n);
void deletetree(node * tree);
bool treecmp(node * tree, int n);

int main(int argc, char const *argv[]) {
freopen("D:\\SJTU\\Freshman Summer\\DS\\test.txt", "r", stdin);
int n;cin >> n;
while (n) {
int l;cin >> l;
node * tree = maketree(n);
for (int i = 0; i < l; i++) {
if (treecmp(tree,n)) cout << "Yes" << endl;
else cout << "No" << endl;
}
deletetree(tree);
cin >> n;
}
return 0;
}

bool check(node * tree, int v)
{
if (!tree) return false;
if (tree->value==v) {
tree->select = 1;
return true;
}
if (tree->select==0) {
return false;
}
if (tree->value>v) {
return check(tree->left,v);
}else{
return check(tree->right,v);
}
}

void settree(node * tree)
{
if (!tree) return;
if (tree->left) settree(tree->left) ;
if (tree->right) settree(tree->right);
tree->select = 0;
}

bool treecmp(node * tree, int n)
{
settree(tree);
int v;
bool ret = true;
for (int i = 0; i < n; i++) {
cin >> v;
if (!check(tree,v)) ret = false;
}
return ret;
}

void deletetree(node * tree)
{
if (!tree) return;
if (tree->left) deletetree(tree->left) ;
if (tree->right) deletetree(tree->right);
delete tree;
}

node * newnode(int value)
{
node * treenode = new node;
treenode->left = NULL ;
treenode->right = NULL ;
treenode->value = value ;
treenode->select = 0 ;
return treenode;
}

node * attachnode(node * tree, int value)
{
if (!tree) {
return newnode(value);
}else{
if (tree->value>value)
tree->left = attachnode(tree->left ,value);
else tree->right= attachnode(tree->right,value);
return tree;
}
}

node * maketree(int n)
{
int value;
node * tree = NULL;
for (int i = 0; i < n; i++) {
cin >> value;
tree = attachnode(tree,value);
}
return tree;
}