LeetCode 96. 不同的二叉搜索树

1、题目

2、分析

假设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;
    }
}