leetcode96M不同的二叉搜索树

思路1：

假设输入为n，输出为f(n)，则选择任意一个数字作为根节点，设左侧节点数为left，右侧节点数为right，那么可组成的二叉搜索树的数量就等于f(left)f(right)，同时当left和right互换时得到的结果相等，即：假如输入为5，那么以1为根节点时，f1(5)=f(0)+f(4),即左侧有0个节点，右侧有4个节点，同样的以5为根节点时f5(5)=f(4)+f(0)=f1(5)，因此f(5)=f1(5)2+f2(5)2+f3(5)；如果输入是偶数，比如6，那么f(6)=f1(6)2+f2(6)2+f3(6)2，（区别在于最后一项是否乘2），基于此思路可以写出如下代码：

    private Map<Integer,Integer> map=new HashMap<Integer,Integer>(); //用来记录已算过的数避免重复计算
    public int numTrees(int n) {
        return core(1,n);
    }
    private int core(int lo,int hi){
        int len=hi-lo+1;
        if(len<3)return len;
        else{
            if(map.get(len)!=null)return map.get(len);
            int sum=0;
            for(int i=1;i<(len>>1);i++){
                sum+=(core(0,i-1)*core(i+1,len-1))<<1;
            }
            sum+=core(lo,hi-1)<<1;
            if((len&1)==1){
                int mid=len>>1;
                sum+=core(0,mid-1)*core(mid+1,len-1);
            }
            map.put(len, sum);
            return sum;
        }
    }

思路2：

因为f(n)只依赖于f(0)-f(n-1)，因此可以用一个一维数组来依次计算f(1),f(2),f(3).....f(n-1),f(n)，计算方法和思路一相同，代码如下：

public int numTrees(int n) {
        if(n<3)return n;
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            int mid=i>>1;
            for(int j=0;j<mid;j++){
                dp[i]+=dp[j]*dp[i-j-1]*2;
            }
            if((i&1)==1){
                dp[i]+=(dp[mid]*dp[mid]);
            }
        }
        return dp[n];
    }

分析：
相比之下方法一更容易想到但是复杂度比第二种方法高，其实两种方法很类似，只是第二种方法存记录的方式使他的读取代价更低（因为采用了定长数组，相比之下HashMap的查找速度肯定是要低于数组的，而且还可能要resize），其实二者的时间复杂度都是O(n^2)，空间复杂度都是O(n)；