题目链接：95. 不同的二叉搜索树 II

题解：

生成所有二叉搜索树！有意思的题！

题目简述：

给定一个序列，生成所有二叉搜索树的序列！

题解：

递归DFS：

对于一个区间的二叉搜索树，我们只需要枚举根节点所在的位置即可，通过递归一步步构建不同的二叉搜索树！

  • 从1 ~ n开始搜索
  • 枚举根节点位置为l ~ r
  • 递归左子树l ~ i - 1，右子树i + 1 ~ r
  • 由于相当于乘法原理，左子树随便一种情况和右子树随便一种情况组合都是一个合法的二叉搜索树
  • 左子树取一种情况，右子树取一种情况，构建根节点，连接起来形成当前结构的二叉搜索树
  • 将当前所有二叉搜索树插入res并返回

递归终止条件：

  • l > r：即为空树，返回NULL
  • n == 0：即输入为0，直接返回空容器{}

注意：

  • 根节点一定要随用随创建，若创建第一层for循环，会导致覆盖情况发生，由于存储的是指针，最后存储将都会是一样的一个二叉树
  • 此处的res不能创建到全局的，那样无法完成下一层向上一层的传递

时间复杂度：是卡特兰数，n个节点构成的二叉搜索树种类是卡特兰数，即 C2nn / n + 1 ！对于n个点的二叉搜索树，方案数如下：

其实推完公式就是卡特兰数，这里就不推了！

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(!n) return {};
        return dfs(1, n);
    }
    vector<TreeNode*> dfs(int l, int r) {
        if(l > r) return {NULL};
        vector<TreeNode*> res;
        for(int i = l; i <= r; i++){
            auto left = dfs(l, i - 1), right = dfs(i + 1, r);
            for(auto& l : left){
                for(auto& r : right){
                    auto root = new TreeNode(i);
                    root->left = l, root->right = r;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};