题解 | #不同的二叉搜索树#

二叉搜索树的概念：
如果某个节点存在左子树，则左子树上的所有节点的值都小于该节点的值；
如果某个节点存在右子树，则右子树上的所有节点的值都大于该节点的值。
因此在明确二叉搜索树的概念之后，我们可以先通过找规律来看数学关系。
n=1......................1
n=2......................2
n=3......................5
n=4......................14
n=5......................42
...
这个结果可以通过下图的图示找到规律

代码如下

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int numTrees(int n) {
        // write code here
        vector<int> res(n+1,0);
        res[0]=0;
        res[1]=1;
        for(int i=2;i<=n;i++)
        {
            if(i<=3)
            {
                res[i]=2*res[i-1]+res[i-2];
                continue;
            }
            int mid=i/2;//注意这里是i，而不是n，因为如果是n的话，会导致n之前的结果有偏差
            res[i] = 2*res[i-1]+2*res[i-2];
            for(int j=2;j<mid;j++)
            {
                res[i] += 2*res[j]*res[i-1-j];
            }
            if(i%2!=0)
            {
                res[i] += res[mid]*res[mid];
            }
        }
        return res[n];
    }
};