//s1 = 1
//s2 = s1*1*2
//s3 = s2*1*2 + s1*s1
//s4 = s3*1*2 + s2*s1*2
//s5 = s4*1*2 + s3*s1*2 + s2*s2
//s6 = s5*1*2 + s4*s1*2 + s3*s2*2
func numTrees(_ n: Int) -> Int {
    guard n > 0 else { return 0 }
    guard n > 1 else { return 1 }
    var arr = Array<Int>(repeating: 0, count: n)
    arr[0] = 1
    for i in 1...n-1 {
        var res = 0
        res += arr[i-1]*2
        for j in 0..<(i-1)/2 {
            res += arr[j]*arr[i-j-2]*2
        }
        if i % 2 == 0 {
            res += arr[(i-1)/2]*arr[(i-1)/2]
        }
        arr[i] = res
    }
    return arr[n-1]
}

不用使用递归Memory使用会大很多。

Runtime: 4 ms, faster than 100.00% of Swift online submissions for Unique Binary Search Trees.
Memory Usage: 18.8 MB, less than 20.00% of Swift online submissions for Unique Binary Search Trees.