Leetcode(96) Unique Binary Search Trees

发表于 | 分类于

Description

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
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

解法

这道题实际上是卡塔兰数的一个例子，类似于斐波那契数。递推发现规律。

对于n = 0，此时为空树，result = 1。

对于n = 1，此时根有一种情况，result = 1。

对于n = 2，此时根有两种情况，result = 根为1的情况+根为2的情况，由于取一个数为根后，探讨一棵树的组成情况，看他的左右子树有多少种组合。对于n = 2，可以左子树放一个点，右子树放零个点，也可以相反，即result[0]*result[1] + result[1]*result[0].

以此类推，n = 3：result[0] * result[2] + result[1]* result[1]+result[2] * result[0].

于是有：

递推公式

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numTrees(int n) {
        List<Integer> dp = new ArrayList<>();
        dp.add(1);
        dp.add(1);
        for (int i = 2; i <= n; i++) {
            dp.add(0);
            for (int j = 0; j < i; j++) {
                int tmp = dp.get(i);
                tmp += dp.get(j) * dp.get(i - 1 - j);
                dp.remove(i);
                dp.add(tmp);
            }
        }
        return dp.get(n);
    }
}