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;
}