原题
给定一个整数 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/
相关推荐
-
leetcode116-填充每个节点的下一个右侧节点指针
原题 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; &...
-
leetcode498-对角线遍历
这是一个Z字形编排问题，JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下...
-
leetcode704-二分查找
原题 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示...
-
leetcode283-移动零
原题 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说...
-
leetcode215-数组中的第K个最大元素
原题 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例1: 输入： [3,2,1,5,6,4] 和...
-
leetcode39-组合总和
原题 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates ...
-
leetcode27-移除元素
原题 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(...
-
leetcode78-子集
原题 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明： 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3...
-
leetcode739-每日温度
原题 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 te...
