Unique Binary Search Tree

题目描述

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         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解题方法

这种求数量的，可以往DP的方向想。

当以i为root时，左子树就是[1:i], 右子树就是[i+1:n+1]构成，而左子树和右子树的root又可以从每一个Index遍历的选一遍。

count[i]表示到正整数i为止的unique bst的数量，其实就是root为0-i都选一遍,可以写几个数的结果来找找感觉。

n = 0: 只能为空,count[0] = 1
n = 1: 一种,count[1] = 1
n = 2: 1可以做root,2也可以做root
    count[2] = count[0] * count[1](1为root) + count[1] * count[0](2为root)
n = 3: 1,2,3都可以做root
    count[3] = count[0] * count[2](1为root) + count[1] * count[1](2为root) + count[2] + count[0](3为root)

可以发现的规律是对于count[i]

for j in range(0, i):
    # 做root的也占据了一个数字,所以是0到i-1
    count[i] += count[j] * count[i-1-j]

Solution

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 1
        count = [0 for i in range(n+1)]
        count[0] = 1

        for i in range(1, n+1):
            for j in range(0, i):
                count[i] += count[j] * count[i-j-1]

        return count[n]

Reference