LeetCode-面试题 04.05: 合法二叉搜索树
First: Problem’s Description
Second: Problem’s Solution
The sequence created when traversing the BST by the method of inorder is a non decreasing sequence. And if the BST is empty, we should return truerather than false
I don’t recommend to use the recrusing method to solve this problem. Take the following ‘BST’ for example:
if you use recrusing method, we can easily submit code like this:
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(!root) return true;
if(root->left && root->left->val >= root->val) return false;
if(root->right && root->right->val <= root->val) return false;
return isValidBST(root->left) && isValid(root->right);
}
};
But there is a fatal bug inside the logic shown from the code: you can make sure that each node complies to the BST’s rule that its left node’s value is always smaller than its and its right node’s value always bigger. but you can’t make sure that every node’s value of the current node’s left subtree is always smaller than current root node and so does right subtree. You can check the node 10and the node 15, and you’ll find the bug.
Third: Code For Solution
class Solution {
private:
vector<int> vec;
void InTraverse(TreeNode* root){
if(root){
InTraverse(root->left);
vec.push_back(root->val);
InTraverse(root->right);
}
}
bool MyJudge(TreeNode* root){
if(!root) return true;
InTraverse(root);
if(vec.size() == 1) return true;
for(int i = 1; i < vec.size(); i++)
if(vec[i - 1] >= vec[i]) return false;
return true;
}
public:
bool isValidBST(TreeNode* root) {
return MyJudge(root);
}
};
