$$\color{Red}{不同的二叉搜索树1【leetcode96 搜索树计数】}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

解析

根据 dp 分析法，其实根据一个节点序列，我们可以枚举根节点 i 作为谁，而为了形成搜索树，显然左子树为 [1, i - 1] 这一段节点，右子树为 [i + 1, n] 这一段节点。

故本质可以从递归分治来解决。但是这道题求方案数的情况下，不在乎数据结构角度的左右节点的细节地址，故其实相同数量节点的构成二叉树搜索树的构成数量是相同的。可以看成只是节点名字一一映射后，但是结构的方案数并没有变化。

故可以直接从节点数出发进行动态规划。

class Solution {
    public int numTrees(int n) {
        int [] f = new int [n + 10];
        f[0] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i; j ++)
                f[i] += f[j - 1] * f[i - j];
        return f[n];
    }
}