美文网首页
LeetCode 96. 不同的二叉搜索树

LeetCode 96. 不同的二叉搜索树

作者: 陈陈chen | 来源:发表于2021-09-15 14:01 被阅读0次

    1、题目

    image.png

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

    相关文章

      网友评论

          本文标题:LeetCode 96. 不同的二叉搜索树

          本文链接:https://www.haomeiwen.com/subject/byncgltx.html