Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
从上图看到需要输出所有搜索树的情况而不是仅仅输出有多少种可能性，为什么我要说这个问题，是因为如果仅仅要输出多少种可能性，可以利用卡特兰数来求解这个问题。先看这个问题。 需要输入所有搜索树的所有可能，给出根节点，首先想到的是回溯求解，博主不才写到一半发现处理不了一个问题就是很难返回root节点，因为递归下去之后满足停止条件时候不知道root节点问题所以困扰许久，看了评论区之后才理解，不多说直接上代码：
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: vector<TreeNode*> generateTrees(int n) { vector<TreeNode*> res; if (n == 0) return res; res = generateTrees(1, n); return res; } private: vector<TreeNode*> generateTrees(int start, int n) { vector<TreeNode*> res; if (start > n) { res.push_back(nullptr); return res; } if (start == n) { res.push_back(new TreeNode(start)); return res; } for (int i = start; i <= n; i++) { vector<TreeNode*>left = generateTrees(start, i - 1); vector<TreeNode*>right = generateTrees(i + 1, n); for (auto& it_l : left) { for (auto& it_r : right) { TreeNode* root = new TreeNode(i); root->left = it_l; root->right = it_r; res.push_back(root); } } } return res; } };每次递归之后都回新建left和right节点数组保存当前root（i）的左右子节点数组，其实可以这么理解，i将[1, n]这个连续区间分成了[1, i-1]和[i+1, n]两个区间，之后在对这两个区间做同样的分解，因此这是一个DP问题。for循环是找出所有根节点的可能情况，代码非常好理解。基于上述我写了一个给定一个任意数组，排列出所有搜索树的可能。 代码如下：
class Solution { public: vector<TreeNode*> generateTrees(vector<int>& nums) { vector<TreeNode*> res; sort(nums.begin(), nums.end()); int m = nums.size(); if (m == 0) return res; res = generateTrees(nums, 0, m - 1); return res; } private: vector<TreeNode*> generateTrees(vector<int>& nums, int start, int end) { vector<TreeNode*> res; if (start > end) { res.push_back(nullptr); return res; } if (start == end) { res.push_back(new TreeNode(nums[start])); return res; } for (int i = start; i <= end; i++) { vector<TreeNode*>left = generateTrees(nums, start, i - 1); vector<TreeNode*>right = generateTrees(nums, i + 1, end); for (auto& it_left : left) { for (auto& it_right : right) { TreeNode* root = new TreeNode(nums[i]); root->left = it_left; root->right = it_right; res.push_back(root); } } } return res; } };思想是一样的，只不过需要首先排序仅此而已。
回到刚开始的问题，如果仅仅是求有多少种可能性，那么可以利用Catalan数来求解问题。 给定一个序列1…n，要从该序列中构造一个二叉搜索树（BST），我们可以枚举序列中的每个数字i，并使用该数字作为根，自然地，子序列1…（i-1）它的左侧将位于根的左分支上，类似地，右子序列（i + 1）… n则位于根的右分支上。然后，我们可以从子序列递归构造子树。通过上述方法，我们可以确保我们构造的BST都是唯一的，因为它们具有唯一的根。 问题是要计算唯一BST的数量。为此，我们需要定义两个函数： G(n)：长度为n的序列的唯一BST数。 F(i, n), 1 <= i <= n：唯一BST的编号，其中编号i是BST的根，序列的范围是1到n。 可以看到，G(n)为了解决问题，我们需要计算的实际函数。并且G(n)可以从导出F(i, n)，最后将递归引用G(n)。 首先，根据上述定义，我们可以看到唯一BST G(n)的总数是F(i)使用每个数字i作为根的BST的总和。 即 G(n) = F(1, n) + F(2, n) + … + F(n, n). 特别是在最底下的情况下，只有一种组合可以构造长度为1（仅根）或0（空树）的BST。 即 G(0)=1, G(1)=1. 给定一个序列1…n，我们从序列中选择一个数字i作为根，然后具有指定根的唯一BST F(i)的数目就是其左和右子树的BST数目的笛卡尔积。例如F(3, 7)：：以3为根的唯一BST树的数量。要以3为根从整个序列[1、2、3、4、5、6、7]构建唯一的BST，也就是说，我们需要从其左子序列[1]构建唯一的BST。 ，2]和右子序列[4、5、6、7]中的另一个BST，然后将它们组合在一起（即笛卡尔乘积）。棘手的部分是，我们可以将序列[1,2]之外G(2)的唯一BST的数量视为，将序列[4，5，6，7]之外的唯一BST的数量视为G(4)。因此，F(3,7) = G(2) * G(4)。 即 F(i, n) = G(i-1) * G(n-i) 1 <= i <= n 结合以上两个公式，我们得到的递归公式G(n)。即 G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 在计算方面，我们需要从较低的数字开始，因为的值G(n)取决于的值G(0) … G(n-1)。
那么leetcode的第96题自然而然就得到了解答：
class Solution { public: int numTrees(int n) { vector<int>dp(n + 1, 0); dp[0] = 1; dp[1] = 1; int res = 0; for (int i = 2; i <= n; i++) for (int j = 1; j <= i; j++) dp[i] += dp[j - 1] * dp[i - j]; return dp[n]; } };