首页 > 代码库 > Validate Binary Search Tree

Validate Binary Search Tree

2024-09-15 08:32:29   216人阅读

方法一：使用递归的方式直接进行判断，也即对于每个节点，其值需要大于左子树最大节点，小于右子树最小节点，但这种方法在leetcode中不能accepted，因为测试集中节点的值有INT_MIN和INT_MAX。。。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr || root->left==nullptr && root->right == nullptr)
            return true;
        
        int min = INT_MAX, max = INT_MIN;
        getValue(root->left, min, max);
        if(root->val <= max)
            return false;
            
        min = INT_MAX, max = INT_MIN;
        getValue(root->right, min, max);
        if(root->val >= min)
            return false;
            
        if(!isValidBST(root->left) || !isValidBST(root->right))
            return false;
        
        return true;
    }
    
    void getValue(TreeNode *root, int &minValue, int &maxValue)
    {
        if(root == nullptr)
            return;
        
        if(root->val > maxValue)
            maxValue = root->val;
        if(root->val < minValue)
            minValue = root->val;
            
        getValue(root->left, minValue, maxValue);
        getValue(root->right, minValue, maxValue);
    }
};

对于上面方法，更简单的写法如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, INT_MIN, INT_MAX);
    }
    
    bool isValidBST(TreeNode *root, int lower, int upper)
    {
        if(root == nullptr)
            return true;
            
        return root->val > lower && root->val < upper && isValidBST(root->left, lower, root->val) && isValidBST(root->right, root->val, upper);
    }
};

方法二：采用中序遍历的方式，若遍历得到的结果呈递增顺序，则是BST

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> result;
        inorder(root, result);
        
        if(result.size() < 2)
            return true;
        
        for(int i=1; i<result.size(); ++i)
            if(result[i] <= result[i-1])
                return false;
        return true;
    }
    
    void inorder(TreeNode *root, vector<int> &result)
    {
        if(root == nullptr)
            return;
            
        if(root->left != nullptr)
            inorder(root->left, result);
            
        result.push_back(root->val);
        
        if(root->right != nullptr)
            inorder(root->right, result);
    }
};

 

Validate Binary Search Tree


联系
我们