[LC]95. 不同的二叉搜索树 II [回溯]

🚩传送门：力扣题目

题目

给你一个整数 ，请你生成并返回所有由 个节点组成且节点值从 到 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例1:

输入：n = 3 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例2:

输入：n = 1 输出：[[1]]

提示：1 <= n <= 8

解题思路：回溯

二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。

假设当前序列长度为 ，如果我们枚举根节点的值为 ，那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为，右子树的节点值的集合为 。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此我们可以想到用回溯的方法来解决这道题目。

步骤

定义 函数表示当前值的集合为 [start,end]，返回序列 生成的所有可行的二叉搜索树。

枚举 中的值 为当前二叉搜索树的根，那么序列可以划分为 和 这两个部分。递归 和 ，获得所有可行的左子树和可行的右子树。最后从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

递归入口为 ，出口为当 的时候，当前二叉搜索树为空，返回空节点。

补充：

整个结果集是用 ListallTrees 存储，每个 ListNode 存放某一二叉搜索树的 Root 结点，最后 List 中会存放所有遍历顺序的 Root 结点

复杂度分析

时间复杂度：

  - 整个算法的时间复杂度取决于「可行二叉搜索树的个数」，而对于 ![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=P02NM) 个点生成的二叉搜索树数量等价于数学上第 ![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=kxAyP) 个「卡特兰数」，用 ![](https://cdn.nlark.com/yuque/__latex/30063be24b6f15f322a50cb09c671ca0.svg#card=math&code=G_n&id=AVMLw) 表示。🚩[卡特兰数具体的细节](https://www.yuque.com/qingxuan-u4juc/leetcode/fgusgi)，这里不再赘述，只给结论。生成一棵二叉搜索树需要 ![](https://cdn.nlark.com/yuque/__latex/e65a67ac353abeeff44c359310d05c02.svg#card=math&code=O%28n%29&id=Zq4sM) 的时间复杂度，一共有 ![](https://cdn.nlark.com/yuque/__latex/30063be24b6f15f322a50cb09c671ca0.svg#card=math&code=G_n&id=wemrB)棵二叉搜索树，也就是 ![](https://cdn.nlark.com/yuque/__latex/0248305477099b65a65e33593fd94f55.svg#card=math&code=O%28n%20%5Ccdot%20G_n%29&id=pRRap)。而卡特兰数以 ![](https://cdn.nlark.com/yuque/__latex/629c9c3572976a4932841fcdc981bddd.svg#card=math&code=%5Cfrac%7B4%5En%7D%7Bn%5E%7B3%2F2%7D%7D&id=sgah8) 增长，因此总时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/4e614bfc275161b65c65afa0201cfa53.svg#card=math&code=O%28%5Cfrac%7B4%5En%7D%7Bn%5E%7B%281%2F2%29%7D%7D%29&id=qmLoF) 。

空间复杂度：

  - ![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=RzOdu) 个点生成的二叉搜索树有 ![](https://cdn.nlark.com/yuque/__latex/30063be24b6f15f322a50cb09c671ca0.svg#card=math&code=G_n&id=IpF7O) 棵，每棵有 ![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=fPme9) 个节点，因此存储的空间需要 ![](https://cdn.nlark.com/yuque/__latex/0684379b84f3815bfd54f77c5e94e3d4.svg#card=math&code=O%28n%20%5Ccdot%20G_n%29%20%3D%20O%28%5Cfrac%7B4%5En%7D%7Bn%5E%7B%281%2F2%29%7D%7D%29&id=tjU1X)，递归函数需要 ![](https://cdn.nlark.com/yuque/__latex/e65a67ac353abeeff44c359310d05c02.svg#card=math&code=O%28n%29&id=tCXq7) 的栈空间，因此总空间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/4e614bfc275161b65c65afa0201cfa53.svg#card=math&code=O%28%5Cfrac%7B4%5En%7D%7Bn%5E%7B%281%2F2%29%7D%7D%29&id=bHwm9) 。

官方代码

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<TreeNode>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            List<TreeNode> leftTrees = generateTrees(start, i - 1);

            // 获得所有可行的右子树集合
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    // 组装出来一个二叉搜索树
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    allTrees.add(currTree);
                }
            }
        }
        return allTrees;
    }
}