leetcode 98题 .验证二叉搜索树

小灰灰 2021-01-10 15:40 572阅读 0赞

**题目描述：**

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTE5NDE1_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTE5NDE1_size_16_color_FFFFFF_t_70 1]  
这里要注意的是：  
要求左子树所有的节点的值都要比根节点要小，并不只是左节点的值  
这里提供了两种方法，第一种是比较简单并且便于理解的方法。

1.  方法一. 中序遍历法

首先我们中序遍历树，中序遍历的顺序是 left -> root -> right。  
所以如果中序遍历后的列表是递增的，那么就是二叉搜索?

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isValidBST(TreeNode root) {
            if(root == null)
                return true;
            //先进行中序遍历，如果遍历后为递增数列则为二叉搜索树
            List<Integer> list = new ArrayList<Integer>();
            inOrder(root,list);
            for(int i=1;i<list.size();i++){
                if(list.get(i-1) >= list.get(i)){
                    return false;
                }
            }
            return true;
        }
        
        private void inOrder(TreeNode node,List<Integer> list){
            //中序遍历二叉搜索树
            if(node == null)
                return;
            inOrder(node.left,list);
            list.add(node.val);
            inOrder(node.right,list);
        }
    }

1.  方法二：递归法

我们这样想，对于整个二叉树的根节点来说，只要左子树的最大值比根节点的值要小，右子树的最小值比根节点的值要大，就可以满足二叉搜索树的特征。  
那么对于左子树来说，又可以转换为同样的问题进行分析，当到了最下方的叶子节点时，最大值和最小值也就是本身，直接return就可以了，这里将大问题拆分为多个子问题，满足了递归的特征。  
代码如下：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isValidBST(TreeNode root) {
            return helper(root,null,null);
        }
        
        private boolean helper(TreeNode root,Integer min,Integer max){
            if(root == null){
                return true;
            }
            //终止条件 左子树最小值 >= 根节点值
            if(min != null && min >= root.val)return false;
            //终止条件 右子树最大值 <= 根节点值
            if(max != null && max <= root.val)return false;
            //递归
            return helper(root.left,min,root.val)&&
            helper(root.right,root.val,max);
        }
    }

**时间复杂度分析：**  
由于两种方法都是将所有节点遍历了一次且仅有一次，所以两个方法的时间复杂度都为O(n)。  
**空间复杂度分析：**  
方法1因为使用了数组，所以空间复杂度为O(n)，而递归法的空间复杂度为O(1)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTE5NDE1_size_16_color_FFFFFF_t_70]: /images/1610293162179.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTE5NDE1_size_16_color_FFFFFF_t_70 1]: /images/1610293183541.png