leetcode96-不同的二叉搜索树

原题

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

发表回复

登录后才能评论