卖萌的弱渣

I am stupid, I am hungry.

Unique Binary Search Trees

Unique Binary Search Trees

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
2
3
4
5

1           3    3       2      1
 \         /    /       / \      \
  3      2     1       1   3      2
 /      /       \                  \
2     1          2                  3

Solution

  • Time: O(n2)
  • count[n]: how many BST trees for n
  • count[0] = 1
  • count[1] = 1
  • count[2] = count[0] * count[1] + count[1] * count[0]
  • count[3] = count[0] * count[2] + count[1] * count[1] + count[2] * count[0]

    count[n] = sum(count[i] * count[n-1-i]) i in [0,n-1]

(Unique-Binary-Search-Trees.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    # @paramn n: An integer
    # @return: An integer
    def numTrees(self, n):
        # write your code here
        # count[n]: number of unique binary search trees for n numbers
        # count[n] = sum(count[i]*[n-1-i]) i in [0,n-1]
        # count[3] = count[0]*count[2] + count[1]*count[1] + count[2]*count[0]
        if n < 2:
            return 1
        count = [0] * (n+1)
        count[0] = 1
        count[1] = 1

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