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

1.题目

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

2.思路分析

• 动态规划
• 对于只有空树和一个节点的情况，那么就只有一种情况
• 给定序列 1 ⋯ n，我们选择数字 i 作为根，则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树。
• 即就是从2到n，将序列分成两个，对于分开的两个部分称为左右子树，然后将左右自己组合（笛卡尔积）
• 举例而言，创建以 3 为根、长度为 7 的不同二叉搜索树，整个序列是 [1, 2, 3, 4, 5, 6, 7]，我们需要从左子序列 [1, 2]构建左子树，从右子序列 [4, 5, 6, 7]构建右子树，然后将它们组合（即笛卡尔积）。
• 利用动态规划的思想，将对应的都写入vector中，返回G[n]即可。

3.代码展示

class Solution {
   public:    int numTrees(int n) {
           vector<int> G(n+1, 0);        G[0] = 1;        G[1] = 1;        for(int i = 2; i <= n; ++i){
               for(int j = 1; j <= i; ++j){
                   G[i] += G[j-1]*G[i-j];            }        }        return G[n];    }};

转载地址：http://bsacz.baihongyu.com/