【刷题日记】二叉树-验证二叉搜索树-L98-Medium
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
学习点
代码
初始版本：
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
| class Solution {
public:
int getMaxVal(TreeNode *root)
{
TreeNode *p = root;
while (p->right)
p = p->right;
return p->val;
}
int getMinVal(TreeNode *root)
{
TreeNode *p = root;
while (p->left)
p = p->left;
return p->val;
}
bool isValidBST(TreeNode* root) {
bool is_left_valid = true;
bool is_right_valid = true;
bool is_root_valid = true;
int left_max_val, right_min_val;
if (root->left)
{
is_left_valid = isValidBST(root->left);
left_max_val = getMaxVal(root->left);
}
if (root->right)
{
is_right_valid = isValidBST(root->right);
right_min_val = getMinVal(root->right);
}
if (root->left)
is_root_valid = is_root_valid && (root->val > left_max_val);
if (root->right)
is_root_valid = is_root_valid && (root->val < right_min_val);
return (is_left_valid && is_right_valid && is_root_valid);
}
};
|
优化版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void traversalBST(TreeNode* root, vector<int>& nodes)
{
if (!root)
return;
traversalBST(root->left, nodes);
nodes.push_back(root->val);
traversalBST(root->right, nodes);
}
bool isValidBST(TreeNode* root)
{
vector<int> nodes;
traversalBST(root, nodes);
for (size_t i = 1; i < nodes.size(); i++)
{
if (nodes[i - 1] >= nodes[i])
return false;
}
return true;
}
};
|
