@(LeetCode)
问题描述
给定一个整数 n，能构造出多少种 BST，使其节点值包括 1~n？
栗子：
输入：3
输出：5
解释：
可构造出 5 种 BST，如下所示：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解题思路
BST，即二叉搜索树，左节点的值小于父节点，右节点的值大于父节点。
根据题意，所要解决的问题是：假设有 1~n 个数字，将其构造成 BST，有多少种方式？
栗子分析
我们先来看几个栗子，手动画图分析一下。
首先，我们需要明确一点，根节点的值可能为 1~n。
-
假设
n=2，那么根节点的值可能为1~2。- 当根节点为
1时，根据BST定义，2只能为右节点。 - 当根节点为
2时，1只能为左节点。
因此，总共有
2种构造方式。图比较简单，就不画了。 - 当根节点为
-
假设
n=3，那么根节点的值可能为1~3。- 当根节点为
1时，2/3只能为右节点，而同时2/3又可以有不同的排布方式。我们能较轻易的推断出其排布为2个节点的构造结果，即当n=2时的结果，为2。 - 当根节点为
2时，1只能为左节点，3只能为右节点，结果为1。 - 当根节点为
3时，1/2只能为左节点，而1/2又可以有2种不同的排布方式，结果为2。
因此，总共有
2 + 1 + 2 = 5种构造方式。可对照问题描述中的栗子。 - 当根节点为
-
假设
n=4，那么根节点的值可能为1~4。-
当根节点为
1时，2/3/4只能为右节点。而2/3/4又可以有不同的排布方式，其排布为3个节点的构造结果，即当n=3时的结果，为5。构造方式如下图所示：
WX20200329-135058@2x.png
-
当根节点为
2时，1只能为左节点，3/4只能为右节点。同理，3/4有不同的构造方式，为2个节点的构造结果，为2。如下图所示：
WX20200329-133549@2x.png
-
当根节点为
3时，1/2只能为左节点，4只能为右节点。同理，1/2的构造方式为2个节点的构造结果，为2。如下图所示：
WX20200329-133603@2x.png
-
当根节点为
4时，1/2/3只能为左节点。同理，1/2/3的构造方式为3个节点的构造结果，为5。如下图所示：
WX20200329-134833@2x.png
因此，总共有
5 + 2 + 2 + 5 = 14种构造方式。 -
-
假设
n=5，那么根节点的值可能为1~5。其分析方式跟上面一样，我们挑一个特殊的值来分析。-
当根节点为
3时，1/2只能为左节点，4/5只能为右节点。因此，左子树的构造方式有2种，右子树的构造方式也有2种，组合起来总共为2 * 2 = 4种。如下图所示：
WX20200329-140451@2x.png
-
规律总结
从以上几个栗子，我们可以得到一些规律：
-
总构造数为根节点分别为
1~n时的构造结果总和。 -
左/右子树的构造结果，可基于先前已计算好的构造结果得出。
-
对于某个根节点来说，其可构造总数为
左子树可构造数 * 右子树可构造数。因此只需要计算出左/右子树的节点数，套用规律2中的结果即可。假设根节点为
i，那么f(i) = f(i-1) * f(n-i)，其中f(i)为构造总数，i-1为左子树节点个数，n-i为右子树节点个数。
因此，根据上述规律，我们可以推导出如下公式。假设 f(n) 为 n 个节点的构造总数。
f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ... + f(n-1) * f(0)
看着这种公式，是不是有点眼熟。对，没错，它就是动态规划的状态转移方程，当前结果根据前面的结果计算得出。
有了解题思路，写代码就简单了。
递归解法
初看推导公式，很容易的想到的是递归解法。我也是采用的这种方式。
为了避免重复计算，使用了 map 来缓存已计算过的值。
js 代码如下：
var numTrees = function(n) {
// 预设值
let map = new Map()
map.set(0, 1)
map.set(1, 1)
map.set(2, 2)
map.set(3, 5)
const result = recursive(n, map)
return result
};
// 89.50%
var recursive = function(n, map) {
if (n >= 0) {
// 直接取值
if (map.has(n)) {
return map.get(n)
}
let i = 1
let sum = 0
while (i <= n) {
sum += recursive(i - 1, map) * recursive(n - i, map)
i += 1
}
// 缓存结果
map.set(n, sum)
return sum
}
return 0
}
非递归解法
其主要思路是提前计算好 1~n 的所有结果，即 f(1), f(2), ..., f(n)，用数组存上 1~n 对应的结果。
这种方式相比递归来说，就是将递归自动帮我们做的事情，手动提前做好。
代码也比较简洁，js 代码如下：
// 非递归
// 96.56%
var numTrees2 = function(n) {
let list = new Array()
// 长度为 n+1
let i = 0
while (i <= n) {
list.push(1)
i += 1
}
// 从 2 开始计算
i = 2
while (i <= n) {
let j = 1
let sum = 0
// 分为左右两部分，去除一个根节点，那么左边为 j - 1 个数，右边 i - j 个数
while (j <= i) {
sum += list[j - 1] * list[i - j]
j += 1
}
list[i] = sum
i += 1
}
// 1-n 的结果已计算完成，直接取值
const result = list[n]
return result
};
网友评论