【LeetCode】Day71-不同的二叉搜索树II&验证二叉搜索树

95. 不同的二叉搜索树 II【中等】

这题的前置题是96. 不同的二叉搜索树，是用的动态规划，但只要求二叉搜索树到的数目，不要求具体排序

如果把 i 当做根节点的话，根据二叉搜索树的性质，[1…i-1]是左子树，[i+1…n]是左子树，递归调用 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

class Solution {
    
    public List generateTrees(int n) {
        return generateTrees(1,n);
    }
    public List generateTrees(int start,int end){
        Listres=new ArrayList<>();
        if(start>end){
            res.add(null);
            return res;
        }
        //i为可行根节点
        for(int i=start;i<=end;i++){
            //所有可能的左子树集合
            Listltrees=generateTrees(start,i-1);
            //所有可能的右子树集合
            Listrtrees=generateTrees(i+1,end);

            for(TreeNode lt:ltrees){
                for(TreeNode rt:rtrees){
                    //从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
                    TreeNode root=new TreeNode(i,lt,rt);
                    res.add(root);
                }
            }
        }
        return res;
    }
}

时间复杂度： O ( n G ( n ) ) O(nG(n)) O(nG(n))，G(n)是卡特兰数

空间复杂度： O ( n G ( n ) ) O(nG(n)) O(nG(n))

• Q:有个问题是start>end时，res.add(null)到底起了什么作用？
• A:如果不加null的话，后面两层for循环无法执行，也就无法建立后续的左右子树

98. 验证二叉搜索树【中等】

简单来说就是递归判断当前节点是否在某个区间内。

有两点需要注意：

1. 每个结点的值都需要是一个范围，仅仅左小右大是不行滴（反例：[5,4,6,null,null,3,7]）
2. 数字范围begin，end类型是long型，int型结果会出错（反例：[-2147483648,-2147483648]）

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

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( n ) O(n) O(n)

这个思路的原理是二叉搜索树的中序遍历序一定是升序的，所以来一遍中序遍历，记录前一个结点的值，看看下一个结点是否大于这个值（即升序）即可

class Solution {
    public boolean isValidBST(TreeNode root) {
        Stackstack=new Stack<>();
        long inorder=Long.MIN_VALUE;
        while(!stack.empty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            //假如中序遍历序不是升序,则不是二叉搜索树
            if(root.val<=inorder)
                return false;
            //记录中序遍历结点的值
            inorder=root.val;
            root=root.right;
        }
        return true;
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( n ) O(n) O(n)