Li Kou 98: verify binary search tree

Power button 98： Verify binary search tree

Title Description

Give you the root node of a binary tree root , Determine whether it is an effective binary search tree .

It works The binary search tree is defined as follows ：

The left subtree of the node contains only Less than Number of current nodes .
The right subtree of the node contains only Greater than Number of current nodes .
All left and right subtrees themselves must also be binary search trees .

I/o sample

 Input ：root = [2,1,3]
 Output ：true

 Input ：root = [5,1,4,null,null,3,6]
 Output ：false
 explain ： The value of the root node is  5 , But the value of the right child node is  4 .

solution 1： Using the idea of recursion

bool isValid(TreeNode *root,long long lower,long long upper)
{
    
    if(root==nullptr)
    {
    
        return true;
    }
    if(root->val<=lower||root->val>=upper)
    {
    
        return false;
    }
    return isValid(root->left,lower,root->val)&&isValid(root->right,root->val,upper);
}


// Use the idea of recursion to realize 
bool isValidBST(TreeNode* root)
{
    
    return isValid(root,LONG_MIN,LONG_MAX);
} 

solution 2： Using middle order traversal

Traversing the binary search tree in medium order, we get an ascending array

// According to the property of ascending order when traversing the binary search tree 
bool isValidBST2(TreeNode* root) 
{
    
    if(!root)
    {
    
        return true;
    }
    stack<TreeNode *>stk;
    vector<int>res;

    while(!stk.empty()||root!=nullptr)
    {
    
        while(root!=nullptr)
        {
    
            stk.push(root);
            root=root->left;
        }

        TreeNode *temp;
        temp=stk.top();
        // cout<<temp->val<<" ";
        res.push_back(temp->val);
        stk.pop();
        root=temp->right;
    }

    int length=res.size();
    for(int i=1;i<length;i++)
    {
    
        if(res[i]<=res[i-1])
        {
    
            return false;
        }
    }
    return true;
}