力扣96 不同的二叉搜索树 java实现

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]; }

以上为记录分享用，代码较差请见谅