leetcode-96-Unique-Binary-Search-Trees

发表于   |  

描述

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

For example,
Given n = 3, there are a total of 5 unique BST’s. 

1
2
3
4
5
1         3     3      2      1
  \       /     /      / \      \
   3     2     1      1   3      2
  /     /       \                 \
 2     1         2                 3

分析

最重要的是找到其中的规律。定义f(n)表示以1..n形成的二叉搜索树的数目，如果n=0，是一种BST，即空树，f(0)=1，n=1，也只有一种情况，f(1)=1，当数组数目大于1，构成的BST树是这样的：以i为根节点，左子树是1..i-1构成的，右边是i+1..n构成的，有多少种情况呢，以i为根节点，情况是：f(i-1)*f(n-i)种，i可取1、2、… n，因此，$f(n)=\sum\limits_{i=1}^{n}f(i-1)*f(n-i)$，至此，就得到动态规划的公式了。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n+1, 0);
        f[0] = 1;
        f[1] = 1;
        for(int i=2; i <= n; i++) {
            for(int k = 1; k <= i; k++) {
                f[i] += f[k-1] * f[i-k];
            }
        }
        return f[n];
    }
};

解决方案2（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[-1]

其实，不用递归也是可以的，这个问题与卡塔兰数有关，一般的数据结构书上也有公式说明。 

1
2
3
4
5
6
7
8
9
import math

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        return math.factorial(2*n)/(math.factorial(n+1)*math.factorial(n))

相关问题

(M) Unique Binary Search Trees II

题目来源