96. Unique Binary Search Trees 不

题目

给定一个整数 n，返回由 1 到 n 组成的所有二叉搜索树的个数。

解析

对于一个二叉搜索树来说，其左节点和右节点分别为二叉搜索树。
所以题目是求
选择 1 left nil～nil right 2~n 所组成的二叉搜索数范围
选择 2 left: 1～1 right: 3～n
选择 3 left: 1～2 right: 4~n
...
选择 n left: 1～(n-1) right: nil~nil
所组成的二叉搜索树。

伪代码

f(m,n) int

if n < m 
  return 1
for  i=m;i<=n;i++
  rst+=f(m,i-1)*f(i+1,n)
return rst

代码

创建一个 []int 用于迭代时快速查询

func numTrees(n int) int {
    mm := make([]int, n)
    return tree(mm, 1,n)
}

func tree(mm []int, m,n int) int {
    if n < m {
        return 1
    }
    if mm[n-m] != 0 {
        return mm[n-m]
    }
    var rst int
    for i:=m;i<=n;i++ {
        rst+=tree(mm, m,i-1)*tree(mm, i+1,n)
    }
    mm[n-m] = rst
    return rst
}

image.png

进一步将这个问题转化为非递归算法。
可以看到，核心算法是 f(m,n) = f(m,k-1)*f(k+1,n)
对于这个问题来说，我们并不关心 m，n 具体值，只是关注元素个数。

f(1) = 1
f(2) = 1*f(1) +  f(1)*1
f(3) = 1*f(2) + f(1)*f(1) + f(2)*1
...
f(n) = 1*f(n-1) + f(1)*f(n-1-1) + ... f(n-1)*1

为了使上式更方便代码实现，引入一个虚拟的 f(0) 代替 1，上述公式可写为
f(n) = f(0)*f(n-1) + ... + f(k)*f(n-1-k) ... +f(n-1)*f(0)

伪代码

f = []int
f[0] = f[1] = 1
for i:=2;i<=n;i++
  for j:=0;j<=n-1;j++
    m[i]+=m[j]*m[i-1-j]
return f[n]

代码

func numTrees(n int) int {
    f := make([]int, n+1)
    f[0] = 1
    f[1] = 1
    for i:=2;i<=n;i++ {
        for k :=0;k<=i-1;k++ {
            f[i]+=f[k]*f[i-1-k]
        }
    }
    return f[n]
}

image.png