• 本题难度: Medium
• Topic: Bit Manipulation

Description

Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?

Example

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

我的代码

class Solution:    """    @param n: An integer    @return: An integer    """    def numTrees(self, n):        # write your code here                A = [1, 1, 2]        if n<3:            return A[n]        for i in range(3,n + 1):            res = 0            for j in range(i):                res += A[j]*A[i - j - 1]            A.append(res)        return A[-1]

思路

假设f(x)为x个结点的不同的二叉搜索树数目。

n个结点的二叉搜索树，可以选取其中任何一个数k为根结点。

则左子树由1～k-1构成，右子树由k+1～n构成。则左子树一共有f(k-1)种情况，右子树有f(n-k-2)种情况。

• 时间复杂度 O(log(n))