96.md

96. Unique Binary Search Trees

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

my thoughts:

1. recursion

my solution:

**********36ms
class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 1:
            return 0
        self.d = {}
        def subTree(start, end):
            if start >= end:
                return 1
            if end-start in self.d:
                return self.d[end-start]
            res = 0
            for i in range(start, end+1):
                left = subTree(start, i-1)
                right = subTree(i+1, end)
                res += left * right
            self.d[end-start] = res
            return res
        return subTree(1,n)

my comments:

from other ppl's solution:

1. dp, 45ms:
class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0:
            return 0
        
        treeNum=[1]*(n+1)
        
        for i in range(1,n+1,1):# 1 to n
            if i==1:
                treeNum[i]=1
            elif i==2:
                treeNum[i]=2
            else:
                cnt=0
                for mid in range(i):# 0 to i-1
                    cnt+=(treeNum[mid]*treeNum[(i-1)-mid])
                treeNum[i]=cnt
                
        return treeNum[n]