🥧中序遍历
二叉搜索树的中序遍历得到的是一个递增的序列。
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
| class Solution {
public:
bool isValidBST(TreeNode* root) {
if(!root)
return true;
vector<int> vec;
helper(root, vec);
if(vec.size() < 2)
return true;
for(int i = 0; i <= vec.size() - 2; ++i) {
if(vec[i] >= vec[i+1])
return false;
}
return true;
}
void helper(TreeNode* root, vector<int>& vec) {
if(!root)
return ;
if(root->left)
helper(root->left, vec);
vec.push_back(root->val);
if(root->right)
helper(root->right, vec);
}
};
|
Accepted
75/75 cases passed (20 ms)
Your runtime beats 49.34 % of cpp submissions
Your memory usage beats 5.03 % of cpp submissions (21.3 MB)
🥧递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool isValidBST(TreeNode* root) {
return check(root, LONG_MIN, LONG_MAX);
}
bool check(TreeNode* root, long low, long high) {
if(!root)
return true;
if(root->val <= low) return false;
if(root->val >= high) return false;
if(!check(root->left, low, root->val) ||
!check(root->right, root->val, high))
return false;
return true;
}
};
|
Accepted
75/75 cases passed (16 ms)
Your runtime beats 76.98 % of cpp submissions
Your memory usage beats 5.07 % of cpp submissions (24 MB)
中序遍历改良
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> stk;
long prev = LONG_MIN;
while(stk.size() || root) {
while(root) {
stk.push(root);
root = root->left;
}
auto top = stk.top();
stk.pop();
if(prev >= top->val)
return false;
prev = top->val;
root = top->right;
}
return true;
}
};
|
Accepted
75/75 cases passed (8 ms)
Your runtime beats 98.79 % of cpp submissions
Your memory usage beats 5.07 % of cpp submissions (24.1 MB)
