题解 | #判断是不是二叉搜索树#

判断是不是二叉搜索树

题目描述

给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

方法一：递归的方法

解题思路

对于本题，采用递归的方法进行求解，对于当前节点，如果其值小于左区间或者大于右区间，返回false。否则，对其左右子树进行递归，采用同样的操作，最后如果没有返回false，则满足题目条件，返回true即可。

解题代码

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root,INT_MIN,INT_MAX);//根节点的区间范围为int的范围
    }
    bool dfs(TreeNode* root,int l,int r){
        if(root==nullptr)
        {
            return true;
        }
        if(root->val<l||root->val>r)//如果当前节点的值小于左区间或者大于右区间，则返回false
        {
            return false;
        }
        return dfs(root->left,l,root->val)&&dfs(root->right,root->val,r);
    }
};

复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用递归，根据栈深度，空间复杂度为$O(logn)O(logn)$，最坏情况为$O(n)O(n)$。

方法二：中序遍历的方法

解题思路

本题目也可也使用中序遍历的方法，二叉搜索树的中序遍历序列一定是从小到大的，因此在中序遍历过程中，如果出现前一个值大于后一个的情况，则说明不满足二叉搜索树。

解题代码

class Solution {
public:
    bool isValidBST(TreeNode* root)
    {
        stack<TreeNode*> st;//初始化
        TreeNode* p=root;
        int pre=INT_MIN;
        while(!st.empty()||p!=nullptr)
        {//栈实现中序遍历
            while(p)
            {
                st.push(p);//入栈
                p=p->left;//遍历左儿子
            }
            p=st.top();
            st.pop();//弹栈
            if(pre>p->val)//中序序列中前一个值大于后一个值，则返回false
                return false;
            pre=p->val;
            p=p->right;//遍历右儿子
        }
        return true;
    }
};

复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用栈需要额外的内存空间，因此空间复杂度为$O(n)O(n)$