LC98 Validate Binary Search Tree

2020-09-09  本文已影响0人  Rookie118

本题链接: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 )


上一篇下一篇

猜你喜欢

热点阅读