作者:贞亭钟_432 | 来源:互联网 | 2023-10-10 07:35
欢迎大家阅读参考,如有错误或疑问请留言纠正,谢谢96UniqueBinarySearchTreesGivenn,howmanystructurallyuniqu
欢迎大家阅读参考,如有错误或疑问请留言纠正,谢谢
96 Unique Binary Search Trees
Given n, how many structurally unique BST‘s (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST‘s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
这题存在一个数学推导式的,复杂度为O(n)。
我采用的是O(n^2)的方法,相对而言直观一点。
令f[n]表示:n个节点有f(n)棵二叉搜索树。
假设已知f[0]~f[n],求f[n+1]:
n+1个节点中有一个是根节点,根节点下左子树设为L,右子树设为R。
Ln表示左子树节点个数,Rn表示右子树节点个数,则Ln + Rn + 1(根节点) = n + 1(总节点个数),即Ln + Rn = n。
那么左子树有f[Ln]种情况,右子树有f[Rn]种情况,因此f[n + 1] = Sigma(f[Ln] * f[Rn])。
class Solution {
public:
int numTrees(int n) {
int f[n+1];
memset (f , 0 , sizeof(int)*(n+1));
f[0]=1;
for(int i=1; i<=n; i++)
for(int j=0; j
leetcode_96_Unique Binary Search Trees