```
class Solution(object):
def numTrees(self, n):
res = [0]*(n+1)
res[0] = res[1] = 1
for i in range(2,n+1):
for j in range(1,1 + i//2):
res[i] += res[j-1] * res[i-j]
res[i] *= 2
if i%2 == 1:
res[i] += res[i//2]**2
return res[n]
```