96. Unique Binary Search Trees

2019-07-29

96. Unique Binary Search Trees

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

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numTrees(self, n: int) -> int:
        T = [1, 1, 2] + [0]*(n - 2)
        for m in range(3, n + 1):
            for i in range(m):
                T[m] += T[i] * T[m - 1 - i]
        return T[n]

    def numTreesFaster(self, n):
        T = [1, 1, 2] + [0]*(n - 2)
        for m in range(3, n + 1):
            mid, remainder = divmod(m, 2)
            for i in range(mid):
                T[m] += T[i] * T[m - 1 - i]
            T[m] *= 2
            if remainder: T[m] += T[mid] * T[mid]
        return T[n]
-->