讲了中序遍历对 BST 的重要意义,写了 BST 的基本操作。

本文循序渐进地讲两道题，如何计算所有有效 BST。

不同的二叉搜索树

力扣第 96 题「 」

固定一个根节点后，其形状总数为左子树的组合数和右子树的组合数乘积

/* 主函数 */
int numTrees(int n) {
          
   
    // 计算闭区间 [1, n] 组成的 BST 个数
    return count(1, n);
}

/* 计算闭区间 [lo, hi] 组成的 BST 个数 */
int count(int lo, int hi) {
          
   
    // base case
    if (lo > hi) return 1;

    int res = 0;
    for (int i = lo; i <= hi; i++) {
          
   
        // i 的值作为根节点 root
        int left = count(lo, i - 1);
        int right = count(i + 1, hi);
        // 左右子树的组合数乘积是 BST 的总数
        res += left * right;
    }

    return res;
}

注意 base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0。

但是这样会出现很多重叠子问题，这时就需要备忘录来记录已经访问过的组合

// 备忘录
int[][] memo;

int numTrees(int n) {
          
   
    // 备忘录的值初始化为 0
    memo = new int[n + 1][n + 1];
    return count(1, n);
}

int count(int lo, int hi) {
          
   
    if (lo > hi) return 1;
    // 查备忘录
    if (memo[lo][hi] != 0) {
          
   
        return memo[lo][hi];
    }

    int res = 0;
    for (int mid = lo; mid <= hi; mid++) {
          
   
        int left = count(lo, mid - 1);
        int right = count(mid + 1, hi);
        res += left * right;
    }
    // 将结果存入备忘录
    memo[lo][hi] = res;

    return res;
}

当然这道题动态规划也可以解决

class Solution {
          
   
    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];
    }
}

不同的二叉搜索树 II

力扣第 95 题「」.让你构建所有 BST

明白了上道题构造合法 BST 的方法，这道题的思路也是一样的：

1、穷举root节点的所有可能。

2、递归构造出左右子树的所有合法 BST。

3、给root节点穷举所有左右子树的组合。

/* 主函数 */
public List<TreeNode> generateTrees(int n) {
          
   
    if (n == 0) return new LinkedList<>();
    // 构造闭区间 [1, n] 组成的 BST 
    return build(1, n);
}

/* 构造闭区间 [lo, hi] 组成的 BST */
List<TreeNode> build(int lo, int hi) {
          
   
    List<TreeNode> res = new LinkedList<>();
    // base case
    if (lo > hi) {
          
   
        res.add(null);
        return res;
    }

    // 1、穷举 root 节点的所有可能。
    for (int i = lo; i <= hi; i++) {
          
   
        // 2、递归构造出左右子树的所有合法 BST。
        List<TreeNode> leftTree = build(lo, i - 1);
        List<TreeNode> rightTree = build(i + 1, hi);
        // 3、给 root 节点穷举所有左右子树的组合。
        for (TreeNode left : leftTree) {
          
   
            for (TreeNode right : rightTree) {
          
   
                // i 作为根节点 root 的值
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                res.add(root);
            }
        }
    }

    return res;
}