96.unique-binary-search-trees.md

给定一个整数 n，求以  1 ... n  为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

---

递归解法

求能组成的二叉搜索树的个数，我们可以依次以每个元素为根，然后左子树的方案数*右子树的方案数，就是以该元素为根的总方案数，将所有总方案数求和，即可得到最终结果

代码实现

var numTrees = function (n) {
  function dfs(min, max) {
    if (min >= max) return 1;
    let counter = 0;
    for (let i = min; i <= max; i++) {
      counter += dfs(min, i - 1) * dfs(i + 1, max);
    }
    return counter;
  }
  return dfs(1, n);
};

class Solution {
    public int numTrees(int n) {
        return dfs(n);
    }

    private int dfs(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dfs(i - 1) * dfs(n - i);
        }
        return ans;
    }
}

{% codetabs name="JavaScript", type="js" -%} var numTrees = function(n) { function dfs(min, max){ if (min >= max) return 1 let counter = 0 for (let i = min; i<=max; i++){ counter += dfs(min, i-1) * dfs(i+1, max) } return counter } return dfs(1, n) }; {%- language name="Java", type="java" -%} class Solution { public int numTrees(int n) { return dfs(n); }

private int dfs(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dfs(i - 1) * dfs(n - i);
    }
    return ans;
}

} {%- endcodetabs %}

效率比较低

动态规划

[1,n]这 n 个数都可以作为根结点，而当 i 成为根节点时，以 i 为根节点的二叉搜索树的个数就是[1,i-1]形成二叉搜索树的个数乘以[i+1,n]形成二叉搜索树的个数

java 代码实现：

class Solution {
    public int numTrees(int n) {
        int h[] = new int[100]; // h[i]表示i个可以组成的搜索树的个数
        h[0] = 1;
        h[1] = 1;
        for (int i = 2; i <= n; i++) { // 遍历个数求h[i]
            for (int root = 1; root <= i; root++) { // 遍历根的所有组成个数
                h[i] += h[root - 1] * h[i - root];
            }
        }
        return h[n];
    }
}

卡特兰数

常用通项公式：

$$h(n)=C_{2*n}^n/(n+1)$$

化简，得到下面代码

代码实现

class Solution {
public:
    int numTrees(int n) {
        long long cnt = 1;
        for (int i = 1; i< n; i++){
            cnt = cnt * (n + i + 1)/ i;
        }
        return cnt / n;
    }
};