LeetCode98—Validate Binary Search Tree

布满荆棘的人生 2022-08-21 02:28 18阅读 0赞

# LeetCode98—Validate Binary Search Tree #

判断是否是查找二叉树，三种方式。

## 原题 ##

> Given a binary tree, determine if it is a valid binary search tree (BST).
> 
> Assume a BST is defined as follows:
> 
> The left subtree of a node contains only nodes with keys less than the node’s key.  
> The right subtree of a node contains only nodes with keys greater than the node’s key.  
> Both the left and right subtrees must also be binary search trees.

判断一棵二叉树是否为二叉查找树（BST）。  
二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：  
若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
任意节点的左、右子树也分别为二叉查找树；  
没有键值相等的节点。

## 分析 ##

### **解法一** ###

二叉查找树有一个重要的性质：即中序遍历递增（不存在两个节点值相等），根据此，中序遍历完成后，查看序列是否有序即可知道是否是二叉查找树。

#### **代码** ####

class Solution {
    private:
        void helper(TreeNode* root,vector<int>&result)//中序遍历
        {
            if (root == NULL)
                return;
            helper(root->left, result);
            result.push_back(root->val);
            helper(root->right, result);
        }
    public:
        bool isValidBST(TreeNode* root) {
            vector<int>result;
            helper(root, result);
            for (int i = 0; i < result.size()-1; i++)
            {
                if (result[i]>result[i + 1])
                    return false;
            }
            return true;
        }
    };

### **解法二** ###

实际上，我们不用完全保存整个序列，这样就不必要再在序列生成之后再迭代判断了。因为中序遍历产生递增序列，所以我们只需记住前一个遍历出来的值，然后与当前值比较即可，如果前一个值大于或等于当前值则返回false。  
这里有个很贱的test case就是他会给你节点值为`INT_MAX`，这样比较的时候没办法完成`>=` 就返回false这个条件了，因为有可能取等号，因为我们的边界就是取得`INT_MAX`，基于此，做小小的修改把`INT_MAX`改成 `numeric_limits<long>::min()`。

#### **代码** ####

class Solution {
    private:
        bool helper(TreeNode * root, long & pre)
        {
            if (root == NULL)
                return true;
            bool left = helper(root->left, pre);
            if (pre >= root->val)
                return false;
            pre = root->val;
            return left && helper(root->right, pre);
        }
    
    public:
        bool isValidBST(TreeNode* root) {
        //  int pre = INT_MIN;
            long pre = numeric_limits<long>::min();
            return helper(root, pre);
        }
    };

### **解法三** ###

这是非常精妙的解法，网上大神的写法，这个实在是没想到：  
对于某个节点p来说：  
以它为根的左子树的范围一定是(MIN , p->val)  
而以它为根的右子树的范围一定是(p->val, MAX)  
这里的MIN和MAX指代负无穷和正无穷，因为左右子树分别只有上界和下界。

这样向下递归的过程中，往左递归时，上界就变成了当前节点的值，往右递归时，下界就变成了当前节点的值。如果在递归中遇到结点值超越了自己的上下界，则返回false，否则返回左右子树的结果。

#### **代码** ####

class Solution {
    private:
        bool helper(TreeNode * root, long  minVal, long maxVal)
        {
            if (root == NULL)
                return true;
            if (minVal >= root->val || maxVal<=root->val)
                return false;
            return helper(root->left, minVal, root->val)&&helper(root->right,root->val,maxVal);
        }
    
    public:
        bool isValidBST(TreeNode* root) {
            //  int pre = INT_MIN;
            long minVal = numeric_limits<long>::min();
            long maxVal = numeric_limits<long>::max();
            return helper(root, minVal,maxVal);
        }
    };