LeetCode 0096 - Unique Binary Search Trees
# Hints
DP
组合数学
卡特兰数
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an integer , return the number of structurally unique BST's (binary search trees) which has exactly nodes of unique values from to .
Example 1:
Input: n = 3
Output: 5
Example 2:
Input: n = 1
Output: 1
Constraints:
# 题意
给定一个正整数 ,求有多少种不同的由键值为 的 个节点组成的二叉查找树的结构。
# 题解
为便于描述,记由键值为 的 个节点组成的二叉查找树为 ,并记 的结构种数为 。
显然,由键值为 的 个节点组成的二叉查找树的结构种数也为 ,因为我们可以将 一一映射到 。
由二叉查找树的性质不难发现,若确定 的根节点为 ,则其左子树中的节点被确定为 ,右子树中的节点被确定为 。那么 以 为根节点的结构种数为其左右子树的结构种数之积,所以 (特别地,令 )。
考虑动态规划,设 。状态转移方程为:
则 即为答案。时间复杂度为 。
事实上,亦可从组合数学的角度考虑,则本题等价于卡特兰数问题,详见:
https://zhuanlan.zhihu.com/p/166135630
# AC代码
class Solution {
public:
int numTrees(int n) {
int dp[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i ++) {
dp[i] = 0;
for (int root = 1; root <= i; root ++) {
dp[i] += dp[root - 1] * dp[i - root];
}
}
return dp[n];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01