两种做法——判断是否是二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150
在这里插入图片描述

方法一：中序遍历

考虑只有两个节点和一个结点的情况，可以头尾各加一个最大最小值，不用特判了，也可以直接特判1和0

由于测试样例里有最大值，所以INT最大值不够用

class Solution {
    List<Long> list = new ArrayList<>();
    public void dfs(TreeNode root){
        if(root==null) return;
        dfs(root.left);
        list.add((long)root.val);
        dfs(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        list.add(Long.MIN_VALUE);
        dfs(root);
        list.add(Long.MAX_VALUE);
        for(int i = 1 ;i < list.size()-1; i++)
            if(list.get(i-1)>=list.get(i)||list.get(i)>=list.get(i+1))
                return false;
        return true;
    }
}

class Solution {
    List<Integer> list = new ArrayList<>();
    public void dfs(TreeNode root){
        if(root==null) return;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        dfs(root);
        if(list.size()==1) return true;
        if(list.size()==2){
            if(list.get(1)>list.get(0)) return true;
            else return false;
        }
        for(int i = 1 ;i < list.size()-1; i++)
            if(list.get(i-1)>=list.get(i)||list.get(i)>=list.get(i+1))
                return false;
        return true;
    }
}

递归法：

非常精妙的区间法，利用区间进行递归。

在这里插入图片描述

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