力扣96——不同的二叉搜索树
原题
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
原题url：https://leetcode-cn.com/problems/unique-binary-search-trees/
解题
这道题看到的第一眼，就和之前的格雷编码一样，又想用动态规划，每次都是遍历所有情况去检查是否有效，但感觉时间复杂度会很高，找找看有没有什么更高效的做法。
所谓高效，也就是寻找规律了，最好的是可以递推，下一次运算可以利用之前的结果，而本题就是用这种规律的。我们来试试 n 等于0、1、2、3的情况：
n = 0，只有1种。
n = 1，也只有1种。
n = 2，有2种
1 2
\ /
2 1
n = 3，有5种
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
让我们回想一下什么叫二叉搜索树，就是针对每个节点，其左子树中所有节点都比它小，其右子树中所有节点都比它大。
再想一下，如果我们针对根选中的情况下，左右子树节点的个数其实也已经定下来了，那么假设同样是 3 个节点，"1、2、3"和"4、5、6"可以组成二叉搜索树，从数量上讲是一样的，因为大小关系没有变。
因此，我们可以说，针对二叉搜索树，其不用考虑值具体是多少，只需要考虑其大小关系即可，那么这就符合上面我所希望的场景了，下一次的运算可以利用之前的结果。
以这道题来说，其具体规律就是：
- 从 1 开始遍历直至 n，以每个节点作为根节点，这样就能计算出左右各个子树的所有节点数。
- 当我们知道了个数，也就可以利用之前计算的结果，获得左右子树可能的情况，两者相乘，也就是在当前根的情况，所有二叉搜索树的情况。
- 将所有根节点的总计算出的数量做累加，也就得出了当前节点数的总情况。
让我们看看代码：
class Solution {
public int numTrees(int n) {
// 存放中间结果
int[] result = new int[n + 1];
result[0] = 1;
result[1] = 1;
for (int i = 2; i <= n; i++) {
int count = 0;
for (int j = 1; j <= i; j++) {
// 左子树总节点数 + 右子树总节点数
count += (result[j - 1] * result[i - j]);
}
result[i] = count;
}
return result[n];
}
}
提交OK， 执行用时：0 ms，内存消耗：33.2 MB。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题目只要利用规律，构造递推关系，也就能解决了。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-01-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录