一、题目
1、算法题目
“给定一个整数n，生成并返回所有由n个节点构成的二叉搜索树。”
题目链接：
来源：力扣（LeetCode）
链接：95. 不同的二叉搜索树 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 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，根节点值为i，那么左子树的节点集合为[1...i-1]，右子树的节点集合为[i 1...n]，当前值的集合为[start,end]，那么就可以将序列分为[start,i-1]和[i-1,end]两部分。
递归调用两部分获得所有可能的左右自述节点，然后从左子树选一个节点，然后从右子树集合中选一个节点拼接到根节点后面，就得到了一颗搜索二叉树。
按照上面的思路找出所有的节点。
2、代码实现
代码参考：
代码语言：javascript复制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;
}
}
3、时间复杂度
时间复杂度 ： O(nGn)
对于n个节点生成的二叉搜索树数量等价于数学上第n个[卡特兰数]，卡特兰数用Gn表示，生成一颗二叉搜索树需要O(n)的时间复杂度，一共有Gn颗二叉搜索树，也就是O(nGn)
空间复杂度： O(nGn)
n个点生成的二叉搜索树有Gn颗，每颗有n个节点，因此空间复杂度为O(nGn)。
三、总结
回溯和递归是穷举题目经常用到的算法，对于这道题来说。
我们只要找到所有的树的节点，然后递归着构造出所有左右子树的组合。
最后找出所有合法的二叉搜索树。
