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