思路： 考虑根节点，设对于任意根节点k，有f(k)种树的可能。 比k小的k-1个元素构成k的左子树。则左子树有f(k-1)种情况。 比k大的n-k个元素构成k的右子树。则右子树有f(n-k)种情况。 易知，左右子树相互独立，所以f(k)=f(k-1)*f(n-k)。 综上，对于n，结果为k取1,2,3,...,n时，所有f(k)的和。
代码思路： 根据上述思路可以用简单的递归方法快速解决。
递归方法：
现在考虑非递归解法，用数组记录每个f(i)的值，记f(0)=1,f(1)=1。 根据公式：f(k)=f(k-1)*f(n-k)，访问数组中的元素。 循环求和，结果更新到数组中。
我设dp[i]表示共有i个节点时，能产生的BST树的个数
n == 0时，空树的个数必然为1，因此dp[0] = 1
n == 1时，只有1这个根节点，数量也为1，因此dp[1] = 1
n == 2时，有两种构造方法
因此，dp[2] = dp[0] * dp[1] + dp[1] * dp[0]
n == 3时，构造方法如题目给的示例所示，dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]
同时，当根节点元素为 1, 2, 3, 4, 5, ..., i, ..., n时，基于以下原则的BST树具有唯一性：
以i为根节点时，其左子树构成为[0,...,i-1],其右子树构成为[i+1,...,n]构成
因此，dp[i] = sigma（dp[0...k] * dp[k+1...i]） 0<= k < i - 1
网友评论