跳转至

96. 不同的二叉搜索树

力扣链接(中等)：https://leetcode.cn/problems/unique-binary-search-trees

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

示例 1：

img

Text Only
1
2
输入：n = 3
输出：5

示例 2：

Text Only
1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 19

个人题解

  1. dp[i] 为由 i 个节点组成的二叉搜索树个数；

  2. 将问题分割为以 1 到 i 作为头节点时，左右子树分别有多少种情况，从而推导出 dp[i] += dp[j - 1] * dp[i - j]。可以根据题目示例1来推导该公式，注：n = 1 有 1 颗二叉搜索树，n = 2 有两颗二叉搜索树，n = 3 时，将其分割为左右子树问题推导；

  3. 由于空树也可以看作一颗二叉搜索树，所以初始化 dp[0] = 1；

  4. 从递推公式可知 i 遍历顺序为从小到大，又因为需要枚举不同值 j 作为头节点，所以需要两层 for 循环；

  5. 手动推导，结果无误！

dp[3] 推导
1
2
3
4
5
6
7
8
init: dp[0] = 1
        [1 作为头节点]    [2 作为头节点]    [3 作为头节点]
dp[1] = dp[0] * dp[0] = 1
dp[2] = dp[0] * dp[1] + dp[1] * dp[0] = 2
dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0] = 5
              1               2               3
             / \             / \             / \
         dp[0] dp[2]     dp[1] dp[1]     dp[2] dp[0]
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numTrees(int n) {
        const int N = 25;
        int dp[N] = {};

        // dp[0] 可以看作一颗空树，所以初始化为 1
        dp[0] = 1;

        for(int i = 1; i <= n; i++) {
            // 枚举从 1 ~ i 作为头节点的情况
            for(int j = 1; j <= i; j++) {
                // BST 左子树小于头节点，右子树大于头节点
                // j - 1 代表左子树节点个数
                // i - j 代表右子树节点个数  
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
};