欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-面试题 04.05: 合法二叉搜索树

程序员文章站 2022-04-24 23:13:23
...

First: Problem’s Description

LeetCode-面试题 04.05: 合法二叉搜索树

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:
LeetCode-面试题 04.05: 合法二叉搜索树
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);
    }
};

Four: Processing Result

LeetCode-面试题 04.05: 合法二叉搜索树

相关标签: LeetCode