1 solutions
-
0
题面描述
塔子哥想构造一棵包含值为1到n的节点的二叉搜索树,并求出所有可能的不同二叉搜索树中,高度不超过k的数量。给定两个整数n和k(满足1 ≤ n, k ≤ 35),请输出符合条件的二叉搜索树的数量。例如,输入为5和4时,输出为26。
思路:动态规划/记忆化搜索
定义有个节点,并且树的高度不超过的情况下,可以构造的二叉查找树的数量。
具体可以使用动态规划或者记忆化搜索来实现
初始状态为,枚举到当前剩余节点个数为时,我们可以分别枚举给左子树分配个节点,右子树分配个节点,并将对应的方案累乘,即为当前的方案数,累加当前方案数即为最终答案
为了避免重复计算,需要使用记忆化搜索
dfs(cnt, dep)
函数表示当前有cnt个节点,树的高度为dep时,能构造出的二叉查找树的数量。如果cnt为0,表示没有节点,那么只能构造出一棵空树,所以返回1。如果dep为0,表示树的高度已经超过了k,那么不能再构造出新的树,所以返回0。
初始状态
-
基础情况:
- 当节点数为 0 时,即
cnt == 0
,返回 1,因为空树是唯一的。 - 当高度
dep == 0
而节点数不为 0 时,返回 0,因为这表示树的高度已经超过了 。
- 当节点数为 0 时,即
-
状态转移:
- 对于每个节点 ,可以选择作为根节点的值,然后分别将剩余的节点分配给左子树和右子树。左子树可以有 个节点,右子树可以有 个节点。
- 对于每种选择,左右子树的组合数量相乘,然后累加到结果中。
代码
C++
python代码
Java代码
-
- 1
Information
- ID
- 70
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 79
- Accepted
- 25
- Uploaded By