原题
给定一个整数 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/
