验证二叉搜索树的几个解法

小咪咪 2022-10-05 01:53 89阅读 0赞

给定一个二叉树，判断其是否是一个有效的二叉搜索树。  
力扣98  
假设一个二叉搜索树具有如下特征：  
节点的左子树只包含小于当前节点的数。  
节点的右子树只包含大于当前节点的数。  
所有左子树和右子树自身必须也是二叉搜索树。

思路 1：中序遍历 为升序则为二叉搜索树

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
          List<Integer> res=new ArrayList<>();
        public boolean isValidBST(TreeNode root) {
        
        //中序遍历为升序
                 if(root==null)
                    return true;
                    inOrder(root);
                 for(int i=1;i<res.size();i++){
        
                        if(res.get(i)<=res.get(i-1)){
        
                            return false;
                        }
                    }
                    return true;
        }
    
        private  void  inOrder(TreeNode root){
        
            if(root!=null){
        
                inOrder(root.left);
                res.add(root.val);
                inOrder(root.right);
            }
    
        }
    }

思路2：  
中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false。

class Solution {
        
        long pre = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            // 访问左子树
            if (!isValidBST(root.left)) {
        
                return false;
            }
            // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
            if (root.val <= pre) {
        
                return false;
            }
            pre = root.val;
            // 访问右子树
            return isValidBST(root.right);
        }
    }
    作者：sweetiee
    链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/zhong-xu-bian-li-qing-song-na-xia-bi-xu-miao-dong-/

思路3：  
思路和算法

要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用，由题目给出的信息我们可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)(l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r)(l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

class Solution {
        
        public boolean isValidBST(TreeNode root) {
        
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
    
        public boolean isValidBST(TreeNode node, long lower, long upper) {
        
            if (node == null) {
        
                return true;
            }
            if (node.val <= lower || node.val >= upper) {
        
                return false;
            }
            return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
        }
    }

注意：知识点  
在JDK中，整形类型是有范围的，最大值为Integer.MAX\_VALUE，即2147483647，最小值为Integer.MIN\_VALUE -2147483648  
Long，short，byte的结论是相同的。