96-题目

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

96-分析

这个问题可以用动态规划的方式解决。我将在下面解释直觉和公式。

给定序列1…n,为了从序列中构造二叉搜索树(BST),我们可以列举序列中的每个数字 i ,并将该数字用作根,自然,其左侧的子序列1…(i-1)将位于根的左分支,类似地,右子序列(i+1)…n位于根的右分支。然后我们可以递归地从子序列构造子树。通过以上方法,我们可以确保我们构建的BST都是独特的,因为它们有独特的根。

问题是要计算唯一的二叉树数量。为此,我们需要定义两个功能:

  • $G(n)$:长度为n的序列的唯一BST数。

  • $F(i,n),1 <= i <= n$:唯一BST的数目,其中 i 是BST的根,序列范围从1到n。

可以看出,G(n)是我们需要计算来解决这个问题的实际函数。G(n)可以从F(i,n)中导出,最后递归地引用G(n)。
首先,给定上面的定义,我们可以看到唯一的BST G(n)的总数,是使用每个数字I作为根的BST F(i)的总和。

$$G(n) = F(1, n) + F(2, n) + … + F(n, n) (1)$$
特别是在下面的情况下,从长度为1(只有根)或0(空树)的序列中,只有一个组合可以构造一个BST。

$$G(0)=1,G(1)=1$$
给定序列1…n,我们从序列中选择一个数字 i 作为根,那么具有指定根F(i)的唯一BST的数量是其左右子树的BST数量的笛卡尔乘积。例如,F(3,7):以数字3为根的唯一BST树的数目。要从以3为根的整个序列[1,2,3,4,5,6,7]中构建一个唯一的边界点,也就是说,我们需要从它的左子序列[1,2]中构建一个唯一的边界点,从右子序列[4,5,6,7]中构建另一个边界点,然后将它们组合在一起(即笛卡尔乘积)。棘手的是,我们可以将[1,2]序列之后的唯一BST的数量当作G(2),将[4,5,6,7]序列外的唯一BST的数量视为G(4)。因此,F(3,7) = G(2) G(4)。即
$$F(i,n)= G(i-1)
G(n-i) 1 <= i <= n (2)$$
结合以上两个公式,我们得到了G(n)的递推公式。即
$$G(n)= G(0) G(n-1)+G(1) G(n-2)+…+G(n-1)* G(0)$$
就计算而言,我们需要从较低的数字开始,因为G(n)的值取决于G(0) … G(n-1)的值。

保存中间结果,在这道题中,中间结果所代表变量是 $G(n)$ 。

96-代码

1
2
3
4
5
6
7
8
9
10
11
public int numTrees(int n) {
int [] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<=i; ++j) {
G[i] += G[j-1] * G[i-j];
}
}

return G[n];
}

95-题目

给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

95-代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<TreeNode> generateTrees(int n) {
return genTrees(1,n);
}
public List<TreeNode> genTrees (int start, int end){
List<TreeNode> list = new ArrayList<TreeNode>();
if(start > end){
list.add(null);
return list;
}
if(start == end){
list.add(new TreeNode(start));
return list;
}
List<TreeNode> left,right;
for(int i = start; i <= end;i++){
left = genTrees(start, i-1);
right = genTrees(i+1, end);
for(TreeNode lnode: left){
for(TreeNode rnode: right){
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
list.add(root);
}
}
}
return list;
}