原题
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解法
思想
对于每一个n对应的数量应该是相同的，我们从1~n中任选一个做根节点（假设是第i个），那么左右两边各有F(i-1)和F(n-i)中情况，将它们相乘就是此时第i个元素做根节点的情况。如此递归计算总数量。
代码
我一开始的写法：
class Solution {
public int numTrees(int n) {
return kindsCount(1,n);
}
public int kindsCount(int start,int end){
if(start >= end) return 1;
int count = 0;
for(int i = start;i<=end;i++){
count += kindsCount(start,i-1)*kindsCount(i+1,end);
}
return count;
}
}
但是发现这样写消耗非常多时间，leetcode执行用时1700 ms。
优化的思路主要是：
1. end和start并不关键，只要start-end（即范围内的数字数量,用n表示）相同，对应的值就相同。
2. 假如优化上条，很多F(n)单元会被重复计算，可以使用数组做缓存。
优化后：
class Solution {
Integer[] cache;
public int numTrees(int n) {
cache = new Integer[n+1];
return kindsCount(n);
}
public int kindsCount(int n){
if(n <= 1) return 1;
if(cache[n]!=null) return cache[n];
int count = 0;
for(int i = 1;i<=n;i++){
count += kindsCount(i-1)*kindsCount(n-i);
}
cache[n] = count;
return count;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode96-%e4%b8%8d%e5%90%8c%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/
相关推荐
-
leetcode1014-最佳观光组合
原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...
-
leetcode322-零钱兑换
原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例 1...
-
leetcode57-插入区间
原题 给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 示例 1: 输入: ...
-
剑指offer51-数组中的逆序对
原题（来源Leetcode） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入： [7...
-
leetcode1111-有效括号的嵌套深度
原题 有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一： 空字符串 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串 嵌套，可以...
-
leetcode73-矩阵置零
原题 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [ [1,1,1], ...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode210-课程表II
原题 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0...
-
leetcode350-两个数组的交集II
原题 给定两个数组，编写一个函数来计算它们的交集。 输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2,2] 示例2： 输入： nums1 = ...
-
leetcode636-函数的独占时间
原题 给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。 每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。 日志是具有以...