96. 不同的二叉搜索树

力扣传送门

中等

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

什么是搜索二叉树？

我们首先来了解一下什么是搜索二叉树吧！

搜索二叉树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它具有以下性质：

1. 对于任意节点，其左子树中的所有节点的值都小于该节点的值。
2. 对于任意节点，其右子树中的所有节点的值都大于该节点的值。
3. 左子树和右子树也都是二叉搜索树。

简单来说，搜索二叉树是按照一定的规则组织节点的二叉树，使得对于任意节点，其左子树的节点值都小于它，右子树的节点值都大于它。这个特性使得在搜索二叉树中进行查找、插入和删除等操作时具有较高的效率。

了解完搜索二叉树我们举一个例子：

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

在这个例子中，每个节点都包含一个值。根节点是4，左子树包含节点2和节点3，右子树包含节点6和节点7。根据搜索二叉树的性质，对于任意节点，其左子树的值都小于它，右子树的值都大于它。

解题思路：

回过头来，我们看这道题目，这道题目描述很简短，刚开始看完之后，一时不知道如何下手，首先这道题目隐藏了一个条件，搜索二叉树，如果不知道这个条件的同学会有点麻烦。

解决这个问题的思路是使用动态规划来逐步构建二叉搜索树，并计算不同结构的数量。

首先，我们可以观察到当根节点的值确定时，左子树和右子树的范围也随之确定。假设根节点的值为 i，那么左子树的节点值范围是从 1 到 i-1，右子树的节点值范围是从 i+1 到 n。

然后，我们可以将问题拆分成子问题。对于每个根节点的值 i，我们可以计算左子树和右子树的不同二叉搜索树的数量，然后将它们相乘，得到以 i 为根节点的不同二叉搜索树的数量。

接下来，我们可以使用动态规划的方法来解决子问题。我们创建一个数组 dp，其中 dp[i] 表示节点数为 i 时的不同二叉搜索树的数量。我们可以从小到大计算 dp 数组的值。

对于节点数为 i，我们遍历根节点的值 j 从 1 到 i，将以 j 为根节点的不同二叉搜索树的数量累加到 dp[i] 中。具体而言，我们可以通过累乘左子树的数量 dp[j-1] 和右子树的数量 dp[i-j] 来计算以 j 为根节点的不同二叉搜索树的数量。

那么有同学会问了，为什么这里要相乘呢？

在计算以 j 为根节点的不同二叉搜索树的数量时，我们需要考虑左子树和右子树的组合情况。

对于左子树，它的节点数量是 j - 1，因为根节点已经被占用了。

对于右子树，它的节点数量是 i - j，因为根节点和左子树的节点已经被占用了。

根据乘法原理，左子树的组合数乘以右子树的组合数，就是以 j 为根节点的不同二叉搜索树的数量。这是因为左子树的每种结构都可以和右子树的每种结构组合，形成一棵以 j 为根节点的二叉搜索树。

因此，我们计算 dp[j - 1] * dp[i - j] 来得到以 j 为根节点的不同二叉搜索树的数量，并将其累加到 dp[i] 中，得到节点数为 i 时的不同二叉搜索树的数量。通过遍历根节点的不同取值 j，我们可以计算出所有节点数的不同二叉搜索树的数量。

最后，计算完 dp 数组后，dp[n] 就是问题的解，即不同结构的二叉搜索树的数量。

综上所述，我们通过逐步构建二叉搜索树，并使用动态规划的思想计算不同结构的数量，解决了这个问题。

代码实现：

class Solution {
    public int numTrees(int n) {
        // 初始化 dp 数组
        int[] dp = new int[n + 1];
        // 初始化 0 个节点和 1 个节点的情况
        dp[0] = 1;
        dp[1] = 1;
    
        // 计算 dp 数组
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // 对于第 i 个节点，需要考虑以 1 到 i 为根节点的情况，所以需要累加
                // 一共 i 个节点，对于根节点 j 时，左子树的节点个数为 j-1，右子树的节点个数为 i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
    
        return dp[n];
    }
}

数形结合：

当 n = 4 时，我们可以通过一个具体的例子来推导一下。

我们要计算节点数为 4 时的不同二叉搜索树的数量。

首先，我们遍历根节点的取值，从 1 到 4。假设根节点的值为 j。

当 j = 1 时，左子树为空，右子树包含节点 2、3、4。此时，左子树的数量为 dp[0]，右子树的数量为 dp[3]。所以以 1 为根节点的不同二叉搜索树的数量为 dp[0] * dp[3] = 1 * 5 = 5。

    1
     \
      2
       \
        3
         \
          4

当 j = 2 时，左子树包含节点 1，右子树包含节点 3、4。此时，左子树的数量为 dp[1]，右子树的数量为 dp[2]。所以以 2 为根节点的不同二叉搜索树的数量为 dp[1] * dp[2] = 1 * 2 = 2。

    2
   / \
  1   3
       \
        4

当 j = 3 时，左子树包含节点 1、2，右子树包含节点 4。此时，左子树的数量为 dp[2]，右子树的数量为 dp[1]。所以以 3 为根节点的不同二叉搜索树的数量为 dp[2] * dp[1] = 2 * 1 = 2。

    3
   / \
  1   4
   \
    2

当 j = 4 时，左子树包含节点 1、2、3，右子树为空。此时，左子树的数量为 dp[3]，右子树的数量为 dp[0]。所以以 4 为根节点的不同二叉搜索树的数量为 dp[3] * dp[0] = 5 * 1 = 5。

    4
   / 
  1 
   \
    2
     \
      3

最后，我们将所有根节点的不同二叉搜索树的数量累加起来，得到节点数为 4 时的不同二叉搜索树的数量：

dp[4] = 5 + 2 + 2 + 5 = 14

所以，当 n = 4 时，不同结构的二叉搜索树的数量为 14。