美文网首页
LC98 Validate Binary Search Tree

LC98 Validate Binary Search Tree

作者: Rookie118 | 来源:发表于2020-09-09 09:13 被阅读0次

    本题链接:Validate Binary Search Tree

    本题标签:Tree, DFS

    本题难度:\color{Orange}{Medium}

    英文题目 中文题目

    方案1:

    
    class Solution {
    private:
        bool checkValid(TreeNode* node, long long low_bound, long long upp_bound)
        {
            if(node == NULL)
                return true;
    
            if(node->val <= low_bound || node->val >= upp_bound)
                return false;
    
            return checkValid(node->left, low_bound, node->val) &&
                   checkValid(node->right, node->val, upp_bound);
        }
    
    public:
        bool isValidBST(TreeNode* root) {
            if(root == NULL)
                return true;
    
            if(root->left == NULL && root->right == NULL)
                return true;
    
            return checkValid(root, numeric_limits<long long>::min(), numeric_limits<long long>::max());
        }
    };
    

    时间复杂度:O ( N )

    空间复杂度:O ( N )


    相关文章

      网友评论

          本文标题:LC98 Validate Binary Search Tree

          本文链接:https://www.haomeiwen.com/subject/rsosektx.html