之前已经有两篇BST的笔记了，特性篇(1038、230、538、剑指54) 讲了中序遍历对BST的重要性，基操篇(450、700、701、98) 写了BST的基本操作。
本文是BST的第三篇，会通过两道题，讲解如何计算所有合法的BST。

96. 不同的二叉搜索树

第一道题是力扣第 96 题「不同的二叉搜索树」，给你输入一个正整数n，请你计算，存储{1,2,3…,n}这些值共有有多少种不同的 BST 结构。
比如说输入n = 3，算法返回 5，因为共有如下 5 种不同的 BST 结构存储{1,2,3}：
image.png
这就是一个正宗的穷举问题，那么如何正确的穷举合法BST的数量呢？
之前说过二叉树算法的关键在于，明确根节点需要做什么，BST作为一种特殊的二叉树，核心思路也是一样的。

举个例子，比如给算法输入n = 5，也就是说用{1,2,3,4,5}这些数字去构造 BST。
首先，这棵 BST 的根节点总共有几种情况？
显然有 5 种情况对吧，因为每个数字都可以作为根节点。
比如说我们固定3作为根节点，这个前提下能有几种不同的 BST 呢？
根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。
所以如果固定3作为根节点，左子树节点就是{1,2}的组合，右子树就是{4,5}的组合。
左子树的组合数和右子树的组合数乘积就是3作为根节点时的 BST 个数。
image.png
我们这是说了3为根节点这一种特殊情况，其实其他的节点也是一样的。
那你可能会问，我们可以一眼看出{1,2}和{4,5}有几种组合，但是怎么让算法进行计算呢？
其实很简单，只需要递归就行了，我们可以写这样一个count函数：

  1. // 主函数
  2. public int numTrees(int n) {
  3.     // 计算闭区间 [1, n] 组成的合法BST数量
  4.     return count(1, n);
  5. }
  7. // 计算闭区间 [lo, hi] 组成的 BST 个数
  8. int count(int lo, int hi){
  9.     // base case
  10.     // 当 lo > hi，闭区间肯定是一个空区间，对应着空节点null，虽然是空节点
  11.     // 但也是一种情况，所以返回1
  12.     if(lo > hi) return 1;
  14.     int res = 0;
  15.     for(int i = lo; i <= hi; i++){
  16.         // i的值作为根节点root
  17.         int left = count(lo, i - 1);
  18.         int right = count(i + 1, hi);
  19.         // 左右子树的组合数乘积是BST的总数
  20.         res += left * right;
  21.     }
  23.     return res;
  24. }

但是，上面的代码时间复杂度太高了，肯定存在重叠子问题，通过不了测试案例。
前文动态规划相关的问题多次讲过消除重叠子问题的方法，无非就是加一个备忘录

  1. // 备忘录
  2. int[][] memo;
  4. // 主函数
  5. public int numTrees(int n) {
  6.     // 备忘录的值初始化为0
  7.     memo = new int[n + 1][n + 1];
  9.     // 计算闭区间 [1, n] 组成的合法BST数量
  10.     return count(1, n);
  11. }
  13. // 计算闭区间 [lo, hi] 组成的 BST 个数
  14. int count(int lo, int hi){
  15.     // base case
  16.     // 当 lo > hi，闭区间肯定是一个空区间，对应着空节点null，虽然是空节点
  17.     // 但也是一种情况，所以返回1
  18.     if(lo > hi) return 1;
  20.     // 查备忘录，如果是重叠子问题，直接从备忘录里取值
  21.     if(memo[lo][hi] != 0){
  22.         return memo[lo][hi];
  23.     }
  25.     int res = 0;
  26.     for(int i = lo; i <= hi; i++){
  27.         // i的值作为根节点root
  28.         int left = count(lo, i - 1);
  29.         int right = count(i + 1, hi);
  30.         // 左右子树的组合数乘积是BST的总数
  31.         res += left * right;
  32.     }
  34.     // 将结果存到备忘录，来避免计算重复子问题
  35.     memo[lo][hi] = res;
  37.     return res;
  38. }

95. 不同的二叉搜索树 II

明白了上道题构造合法 BST 的方法，这道题的思路也是一样的：
1、穷举root节点的所有可能。
2、递归构造出左右子树的所有合法 BST。
3、给root节点穷举所有左右子树的组合。

  1. // 主函数
  2. public List<TreeNode> generateTrees(int n) {
  3.     if(n == 0) return new LinkedList<>();
  4.     // 构造闭区间 [1, n] 组成的BST
  5.     return build(1, n);
  6. }
  8. // 构造闭区间 [lo, hi] 组成的 BST
  9. List<TreeNode> build(int lo, int hi){
  10.     List<TreeNode> res = new LinkedList<>();
  12.     // base case
  13.     if(lo > hi){
  14.         // 当 lo > hi，闭区间肯定是一个空区间，对应着空节点null
  15.         res.add(null);
  16.         return res;
  17.     }
  19.     // 1、穷举 root 节点的所有可能
  20.     for(int i = lo; i <= hi; i++){
  21.         // 2、递归构造出左右子树的所有合法BST
  22.         List<TreeNode> leftTree = build(lo, i - 1);
  23.         List<TreeNode> rightTree = build(i + 1, hi);
  24.         // 3、给 root 节点穷举所有左右子树的组合
  25.         for(TreeNode left : leftTree){
  26.             for(TreeNode right : rightTree){
  27.                 // i 作为节点 root 的值
  28.                 TreeNode root = new TreeNode(i);
  29.                 root.left = left;
  30.                 root.right = right;
  31.                 res.add(root);
  32.             }
  33.         }
  34.     }
  36.     return res;
  37. }