算法笔记_面试题_5.验证二叉搜索树

╰半夏微凉° 2023-02-20 07:40 76阅读 0赞

# 题目 #

[98. 验证二叉搜索树][98.]

难度：中等

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

*  节点的左子树只包含**小于**当前节点的数。
 *  节点的右子树只包含**大于**当前节点的数。
 *  所有左子树和右子树自身必须也是二叉搜索树。

**示例 1:**

输入:
        2
       / \
      1   3
    输出: true

**示例 2:**

输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ，但是其右子节点值为 4 。

# 解法 #

## 中序遍历的方法： ##

vector<int> result;   
    bool isValidBST(TreeNode* root) {
        inorderTraversal(root);
        if (result.size()<=1) return true;
        for(int i=0; i<result.size()-1; i++){
            if(result[i]>=result[i+1]) 
               return false;
       }
        return true;
    }
    
    vector<int> inorderTraversal(TreeNode* root){
        if(root != NULL){
            inorderTraversal(root->left);
            result.push_back(root->val);
            inorderTraversal(root->right);
        }
        return result;
    }

时间复杂度较高O(2n), 空间复杂度O(n)

## 递归写法 ##

思想：

*  先设定两个哨兵（最大值、最小值）；
 *  定义好递归退出条件（root为空时为true退出，root值大于最大或者root值小于最下时为false退出）；
 *  当树为一个合格的二叉搜索树时，总是 左子数值 < 当前根节点 < 右子树值；
    
     *  此时若将左节点作为根节点、LONG\_MIN最为最小值、当前根的值为最大值进行判断；
     *  此时若将右节点作为根节点、当前根的值为最小值、LONG\_MAX最最大值进行判断。

bool isValidBST(TreeNode* root) {
        //最开始使用两个极值最为上下阶
        return  recurse(root, LONG_MIN, LONG_MAX);
    }
    
    bool recurse(TreeNode* root, long long min, long long max){
        if (!root) return true;  //验证到最后，根节点为空时，就可以返回true了
        else if(root->val >= max || root->val <= min)  // 注意等于号别少
            return false;
        //作为左子节点，根节点当成上限，作为右子节点时，根节点作为下限
        else 
            return recurse(root->left, min, root->val) && recurse(root->right, root->val, max);
    }

### 复杂度分析 ###

时间复杂度 : O(n)，其中 nn 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。

空间复杂度 : O(n)，其中 nn 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n)。

[98.]: https://leetcode-cn.com/problems/validate-binary-search-tree/