一、题目
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、代码实现
代码参考：
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)。
三、总结
回溯和递归是穷举题目经常用到的算法，对于这道题来说。
我们只要找到所有的树的节点，然后递归着构造出所有左右子树的组合。
最后找出所有合法的二叉搜索树。
