本文共 1096 字，大约阅读时间需要 3 分钟。

先给出一种自己的做法：时间O(N^3)，可以AC

直觉是n节点二叉搜索树的结构是通过n-1节点扩展出来的，且有一定规律。

花了15分钟，貌似找到了这个规律：

因为新插入的点一定是最大的，所以可以通过插缝的方式插入新节点n，但是有些是不满足二叉搜索树的排序关系，去掉后就是如图的逻辑关系。

class Solution {public:    int numTrees(int n) {        int dp[n+1][n+1];        memset(dp,0,sizeof(dp));        dp[1][1] = 1;        for(int i=2;i<=n;i++){            for(int j=1;j<=i;j++){                for(int k=j-1;k

进阶版，O(N^2)的做法：

时间压缩一下，类似于快速幂的思路，

把每个值都轮番作为根节点，由于二叉搜索树的特性，左子树上节点集合一定比根小，右子树节点集合一定比根大，所以相当于递归处理。

class Solution {public:    int numTrees(int n) {        int dp[n+1];        memset(dp,0,sizeof(dp));        dp[0] = dp[1] = 1;        for(int i=2;i<=n;i++){            for(int j=0;j

究极版，O(N)的做法：

根据进阶版递归公式

这个东西叫做Catalan数：

快速计算公式：

f(n) = C(2n,n) / (n+1)

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

注：ans一定要用long long，否则会溢出，这里只能先乘n+i再除i，否则可能出现整数除法错误。

转载地址：https://blog.csdn.net/ShellDawn/article/details/99806660 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！