Leetcode 96.不同的二叉搜索树

题目描述：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

1
2

输入：n = 3
输出：5

示例 2：

1
2

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

链接：

https://leetcode-cn.com/problems/unique-binary-search-trees

题目分析

  二叉搜索树也即中序遍历是一致的（升序序列）。我们分析一下结点数为 n 时，有几种不同的情况呢？我们设根结点为第 i 个数，则在 i 的左边的所有数构成左子树，右边所有的数构成右子树。我们设结点数为 n 的二叉搜索树种数为 $f(n)$，那么其实左子树的种数就为 $f(i-1)$，右子树的种数为 $f(n-i)$。而我们一共可以有 n 个数可以成为根结点，也即有如下递推公式，其中 $f(0)=1$。

  这其实就是我们曾经接触过的卡特兰数。而第 $n$ 个卡特兰数计算公式为 $\displaystyle\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}$。需要注意的是必须使用 long long int 类型才不会越界。

1
2
3
4
5
6
7
8
9
10
11
12

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

  时间复杂度：$O(n)$，其中 $n$ 为二叉搜索树的结点数。计算卡特兰数用到了一个 $O(n)$ 的循环。
  空间复杂度：$O(1)$。我们只需要常数的空间存放变量。