1、题目
image.png2、分析
假设n=5,也就是使用1、2、3、4、5这五个数来组合成BTS。
根节点有5种情况,我们假设使用3来作为根节点,那么左子树就有1、2来做BTS,右子树由4、5来做BTS。所以用3作为根节点的时候,不同的BTS的种类有:1、2作为左子树的种类 * 3、4作为右子树的种类。
那1、2和3、4的子树有多少种BTS的可能呢?递归来求就好了。
3、代码
class Solution {
int[][] memo; //用来记录重复的结果,避免重复计算
public int numTrees(int n) {
memo = new int[n + 1][n + 1];
return count(1, n);
}
private int count(int lo, int hi){
if(lo > hi) return 1;
if(memo[lo][hi] != 0){
return memo[lo][hi];
}
int res = 0;
for(int i = lo; i <= hi; i++){
int left = count(lo, i - 1);
int rigth = count(i + 1, hi);
res += left * rigth;
}
memo[lo][hi] = res;
return res;
}
}
网友评论