Skip to content

Commit 52eea9a

Browse files
gatiemegatieme
authored
Merge pull request gatieme#2 from neycyanshi/neycyanshi-patch-1
Update 024-二叉搜索树的后序遍历序列/bruteforce.cpp
2 parents 83ca915 + fd03b2d commit 52eea9a

File tree

2 files changed

+43
-63
lines changed

2 files changed

+43
-63
lines changed

‎024-二叉搜索树的后序遍历序列/README.md

Lines changed: 21 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -94,38 +94,28 @@
9494
class Solution
9595
{
9696
public:
97-
bool VerifySquenceOfBST(vector<int> sequence)
98-
{
99-
int left = 0, right = sequence.size( ) - 1;
100-
while(left < right && right != 0)
101-
{
102-
// 前一半的元素都小于size
103-
while(sequence[left] < sequence[right])
104-
{
105-
left++;
106-
}
107-
// 循环结束时, left是第一个大于根的元素的位置
108-
//
109-
while(sequence[left] > sequence[right])
110-
{
111-
left++;
112-
}
113-
114-
right--;
115-
}
116-
117-
// 如果循环一直走到right == 0才终止, 说明满足后序遍历的定义
118-
if(right == 0)
119-
{
120-
return true;
121-
}
122-
else // 否则说明不满足递归的定义
123-
{
124-
return false;
125-
}
126-
97+
//下面这种迭代的方法时间复杂度为O(n^2)
98+
bool VerifySquenceOfBST_Iteratively(const vector<int>& sequence) {
99+
int left = 0, right = sequence.size() - 1;
100+
while (left < right && right != 0) {
101+
//循环结束时，left是第一个大于根的元素的位置，即右子树首元素下标
102+
while (sequence[left] < sequence[right])
103+
left++;
104+
//循环结束时，left越过右子树末节点，到达根节点
105+
while (sequence[left] > sequence[right])
106+
left++;
107+
108+
//如果没有到达根节点，说明不满足左子树所有节点小于根节点，右子树所有节点大于根节点的条件
109+
if (left < right)
110+
return false;
111+
left = 0;
112+
113+
right--;
114+
}
127115

128-
}
116+
//如果循环一直到right == 0才终止, 说明以所有节点为根节点，左侧序列均满足后序遍历序列的条件
117+
return (right == 0) ? true : false;
118+
}
129119
};
130120
```
131121

‎024-二叉搜索树的后序遍历序列/bruteforce.cpp

Lines changed: 22 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -19,38 +19,28 @@ using namespace std;
1919
class Solution
2020
{
2121
public:
22-
bool VerifySquenceOfBST(vector<int> sequence)
23-
{
24-
int left = 0, right = sequence.size( ) - 1;
25-
while(left < right && right != 0)
26-
{
27-
// 前一半的元素都小于size
28-
while(sequence[left] < sequence[right])
29-
{
30-
left++;
31-
}
32-
// 循环结束时, left是第一个大于根的元素的位置
33-
//
34-
while(sequence[left] > sequence[right])
35-
{
36-
left++;
37-
}
38-
39-
right--;
40-
}
41-
42-
// 如果循环一直走到right == 0才终止, 说明满足后序遍历的定义
43-
if(right == 0)
44-
{
45-
return true;
46-
}
47-
else // 否则说明不满足递归的定义
48-
{
49-
return false;
50-
}
51-
52-
53-
}
22+
//下面这种迭代的方法时间复杂度为O(n^2)
23+
bool VerifySquenceOfBST_Iteratively(const vector<int>& sequence) {
24+
int left = 0, right = sequence.size() - 1;
25+
while (left < right && right != 0) {
26+
//循环结束时，left是第一个大于根的元素的位置，即右子树首元素下标
27+
while (sequence[left] < sequence[right])
28+
left++;
29+
//循环结束时，left越过右子树末节点，到达根节点
30+
while (sequence[left] > sequence[right])
31+
left++;
32+
33+
//如果没有到达根节点，说明不满足左子树所有节点小于根节点，右子树所有节点大于根节点的条件
34+
if (left < right)
35+
return false;
36+
left = 0;
37+
38+
right--;
39+
}
40+
41+
//如果循环一直到right == 0才终止, 说明以所有节点为根节点，左侧序列均满足后序遍历序列的条件
42+
return (right == 0) ? true : false;
43+
}
5444
};
5545

5646

0 commit comments

Comments
 (0)