96.不同的二叉搜索树
给你一个整数n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3输出：5
示例 2：
输入：n = 1输出：1
提示：
1 <= n <= 19
如图所示：
当n为3的时候有以下情况：
当1为头结点的时候，其右子树有两个节点
当2为头结点的时候，其左右子树都只有一个节点
当3为头结点的时候，其左子树有两个节点
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
由此可推出递归的规律。
public static void main(String[] args) { // 测试用 System.out.println(numTrees(3)); } public static int numTrees(int n) { int[] res = new int[n + 1]; res[0] = 1; res[1] = 1; for (int i = 2; i <= n; i++) { int sum = 0; for (int j = 1; j <= i; j++) { sum = sum + res[j - 1] * res[i - j]; } res[i] = sum; } System.out.println(Arrays.toString(res)); // 观测每个数量的不同二叉搜索树 return res[n]; }以上为记录分享用，代码较差请见谅
