leetcode二叉树系列(二叉搜索树篇)

目录

1、不同的二叉搜索树

2、验证二叉搜索树

---

1、不同的二叉搜索树

不同的二叉搜索树

题目描述：

 思路：既然要我们求n个节点组成的二叉搜索树，就可以看作是求当根节点为1组成的二叉搜索树+根节点为2组成的二叉搜索树+根节点为3构成的二叉搜索树+……

G(n) = f(1) + f(2) + f(3) +……

而根节点为1组成的二叉搜索树有多少种呢，根节点不变，左边节点构成的二叉搜索树个数*右边节点构成的二叉搜索树个数

由于是二叉搜索树，左边结点的个数就是(根节点-1)，右边结点的个数(总结点数-根节点）

f(1) = G(0)*G(n-1) ,同样的f(2) = G(1)*G(n-2),f(3) = G(2)*G(n-3)……

f(i) = G(i-1)*G(n-i)

两个公式合起来

G(n) = G(0)*G(n-1) + G(1)*G(n-2) + G(2)*G(n-3)+……

这就是我们大名鼎鼎的卡特兰数公式!

得到这个规律，我们思路瞬间就清晰了，这不就是典型的动态规划嘛，咱们直接遍历，从dp[2]，直到求到dp[n]

进入代码：

public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i<= n;i++){
            for(int j = 1 ; j <= i ; j++ ){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

2、验证二叉搜索树

验证二叉搜索树

题目描述：

 

 思路：二叉搜索树，就是要求左边节点值小于根节点，根节点小于右边节点，所以我们要判断是否为二叉搜索树，最好的办法就是利用中序遍历，不断遍历，不断比较；

而且是典型的递归问题，我们先要递归到左子树的最左节点，然后把这个最左结点的值记录下来pre，回溯回来与它的根节点比较，然后再向当前根节点的根节点递归，依次比较，当我们左子树递归结束后，此时pre的值是左子树的最右节点，这是左子树的最大值，我们又与根节点root比较，再进入右子树递归；

直接看代码：

 long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        if(!isValidBST(root.left)) return false;

        if(root.val <= pre) return false;
        pre = root.val;

        return isValidBST(root.right);
    }

只要思路清晰了，代码很好写出来!

持续更新中~~