1.题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
2.思路
（1）递归
参考LeetCode_二叉搜索树_中等_95.不同的二叉搜索树 II这题中的思想，先构造出所有的满足题意的二叉搜索树，然后再计算它们的种数即可。不过显然这种做法的效率非常低，因为题目只需要计算满足题意的二叉搜索树的种数，中间构造具体的二叉树会消耗大量的时间，所以在LeetCode上测试时会出现运行超时的情况！
（2）动态规划_递归
3.代码实现（Java）
//思路1————递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int numTrees(int n) {
//构造节点值区间[1, n]组成的BST
return build(1, n).size();
}
public List<TreeNode> build(int low, int high) {
//res用于保存所有的二叉搜索树（BST）
List<TreeNode> res = new ArrayList<>();
if (low > high) {
res.add(null);
return res;
}
//穷举所有可能的root节点值
for (int i = low; i <= high; i++) {
//递归构造当前根节点的所有合法的左右BST
List<TreeNode> leftTree = build(low, i - 1);
List<TreeNode> rightTree = build(i + 1, high);
//穷举所有的组合
for (TreeNode left : leftTree) {
for (TreeNode right : rightTree) {
//i为根节点的值
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
//将当前的一个解保存到res中
res.add(root);
}
}
}
return res;
}
}
//思路2————动态规划_递归
class Solution {
//dp[i][j]:表示使用区间[i, j]中的所有整数构造的不同二叉树的种类
int[][] dp;
public int numTrees(int n) {
//初始化dp，默认值为0
dp = new int[n + 1][n + 1];
//计算使用区间[1, n]中的所有整数构造的不同二叉树的种类
return calCnt(1, n);
}
public int calCnt(int low, int high) {
if(low > high) {
return 1;
}
if (dp[low][high] != 0) {
return dp[low][high];
}
int res = 0;
//将mid看作根节点的值，那么穷举mid所有可能的取值情况
for (int mid = low; mid <= high; mid++) {
//计算左子树节点值区间[low, mid - 1]可以构造的不同二叉树的种类
int leftCnt = calCnt(low, mid - 1);
//计算右子树节点值区间[mid + 1, high]可以构造的不同二叉树的种类
int rightCnt = calCnt(mid + 1, high);
//简单组合得到当前根节点值为mid的不同二叉树的种类
res += leftCnt * rightCnt;
}
//将结果存入res中
dp[low][high] = res;
return res;
}
}