链接
https://leetcode-cn.com/problems/unique-binary-search-trees/
耗时
解题：51 min
题解：36 min
题意
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
思路
透过现象看本质。画图找规律。从1画到4，在画的时候，发现当整数的个数相同时，其实无论它们的数值是什么，二叉搜索树的种数是一样的，比如：以 1 … 3 为节点 和 以 2 … 4 为节点组成的二叉搜索树的个数相同。并且以 1 … n 为节点组成的二叉搜索树可以将 1 … n 任意一个数作为根节点，那么其左子树可以有 0~n-1 个节点（根节点为1时，左子树有0个节点，根节点为2时，左子树有1个节点，，，），相应地，当左子树有 i 个节点时，右子树对应有 n-1-i 个节点，而且此时的二叉搜索树种数 应该是 左子树（i个节点）的种数 乘以 右子树（n-1-i 个节点）的种数。如果用 f[i] 表示 以 i 为节点组成的二叉搜索树的种数，那么其中
当
左
子
树
有
j
个
节
点
时
的
二
叉
搜
索
树
的
种
数
=
f
[
j
]
∗
f
[
i
−
1
−
j
]
当左子树有 j 个节点时的二叉搜索树的种数 = f[j]*f[i-1-j]
当左子树有j个节点时的二叉搜索树的种数=f[j]∗f[i−1−j]。最终，以 1 … n 为节点组成的二叉搜索树的种数就应当是将左子树的节点数为 0~n-1 时的二叉搜索树的种数加起来。
f
[
i
]
=
∑
j
=
0
i
−
1
f
[
j
]
∗
f
[
i
−
1
−
j
]
f[i]=\sum_{j=0}^{i-1} f[j]*f[i-1-j]
f[i]=j=0∑i−1f[j]∗f[i−1−j]
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
AC代码
class Solution {
public:
int numTrees(int n) {
vector<int> f(n+1, 0);
f[0] = f[1] = 1;
for(int i = 2; i <= n; ++i) {
for(int j = 0; j < i; ++j) {
f[i] += f[j]*f[i-1-j];
}
}
return f[n];
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
