-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path33_SquenceOfBST.cpp
More file actions
159 lines (135 loc) · 3.21 KB
/
33_SquenceOfBST.cpp
File metadata and controls
159 lines (135 loc) · 3.21 KB
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.
Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************/
//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================
// 面试题33：二叉搜索树的后序遍历序列
// 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
// 如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
#include <cstdio>
// BST：Binary Search Tree，二叉搜索树
bool VerifySquenceOfBST(int sequence[], int length)
{
if(sequence == nullptr || length <= 0)
return false;
int root = sequence[length - 1];
// 在二叉搜索树中左子树的结点小于根结点
int i = 0;
for(; i < length - 1; ++ i)
{
if(sequence[i] > root)
break;
}
// 在二叉搜索树中右子树的结点大于根结点
int j = i;
for(; j < length - 1; ++ j)
{
if(sequence[j] < root)
return false;
}
// 判断左子树是不是二叉搜索树
bool left = true;
if(i > 0)
left = VerifySquenceOfBST(sequence, i);
// 判断右子树是不是二叉搜索树
bool right = true;
if(i < length - 1)
right = VerifySquenceOfBST(sequence + i, length - i - 1);
return (left && right);
}
// ====================测试代码====================
void Test(const char* testName, int sequence[], int length, bool expected)
{
if(testName != nullptr)
printf("%s begins: ", testName);
if(VerifySquenceOfBST(sequence, length) == expected)
printf("passed.\n");
else
printf("failed.\n");
}
// 10
// / \
// 6 14
// /\ /\
// 4 8 12 16
void Test1()
{
int data[] = {4, 8, 6, 12, 16, 14, 10};
Test("Test1", data, sizeof(data)/sizeof(int), true);
}
// 5
// / \
// 4 7
// /
// 6
void Test2()
{
int data[] = {4, 6, 7, 5};
Test("Test2", data, sizeof(data)/sizeof(int), true);
}
// 5
// /
// 4
// /
// 3
// /
// 2
// /
// 1
void Test3()
{
int data[] = {1, 2, 3, 4, 5};
Test("Test3", data, sizeof(data)/sizeof(int), true);
}
// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
void Test4()
{
int data[] = {5, 4, 3, 2, 1};
Test("Test4", data, sizeof(data)/sizeof(int), true);
}
// 树中只有1个结点
void Test5()
{
int data[] = {5};
Test("Test5", data, sizeof(data)/sizeof(int), true);
}
void Test6()
{
int data[] = {7, 4, 6, 5};
Test("Test6", data, sizeof(data)/sizeof(int), false);
}
void Test7()
{
int data[] = {4, 6, 12, 8, 16, 14, 10};
Test("Test7", data, sizeof(data)/sizeof(int), false);
}
void Test8()
{
Test("Test8", nullptr, 0, false);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
return 0;
}