专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友冷嘲热讽的发文称：原来小红书还在大小周啊，真可怜。其中一位小红书的员工回到：不用可怜，双倍工资，盼着每周多加几天呢。如果周末加班真的是双倍工资，确实很良心了，估计也会有不少人盼着周末加班。
在互联网行业周末加班还给工资的确实不多，我之前工作过的一些公司无论是工作日加班还是周末加班，都会记录加班时长，可以用来调休，从来不会算到工资上的，到最后裁员的时候，如果没有调休完，有的会给你折算成赔偿，有的直接不算，等于白加了，能把加班折算成双倍工资的真的不多见。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第95. 不同的二叉搜索树 II。
问题描述
来源：LeetCode第95题
难度：中等
给你一个整数 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 <= 8
问题分析
这题让用 n 个整数构成不同的二叉搜索树，关于二叉搜索树的更多知识可以看下前面讲的。因为二叉搜索树左子树上的所有节点都小于根节点，右子树上的所有节点都大于根节点。
我们可以选择任何一个数字把它当做根节点，它左边的所有数字构成左子树，右边的所有数字构成右子树。比如 n 等于 8 ，我们可以选择 3 作为根节点，左边的所有数字[1,2]构成左子树，右边的所有数字[4,5,6,7,8]构成右子树。这里除了选择 3 以外我们还可以选择任何其他数字当做根节点，只需要枚举即可。
然后左子树和右子树的构建可以使用同样的方式，所以这是一个 分治算法 。先通过枚举的方式确定根节点，然后通过递归的方式创建左右子树，因为左子树和右子树可能有多个，所以要通过自由组合的方式来创建该二叉树。
JAVA：
public List generateTrees (int n) {
return generateTrees(1, n);
}
// 左闭右闭区间[start,end]
public List generateTrees (int start, int end) {
List
mList = new ArrayList<>(); if (start > end) { // 无效区间 mList.add( null); return mList; } // 区间继续分成三部分，其中[i]是当前节点，[start, i - 1]是当前节点的所有 // 左子节点，[i + 1, end]是当前节点的所有右子节点，左右子节点继续递归创建。 for ( int i = start; i <= end; i++) { // 递归创建左子树 List leftTrees = generateTrees(start, i - 1); // 递归创建右子树 List rightTrees = generateTrees(i + 1, end); // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上 for (TreeNode left : leftTrees) { for (TreeNode right : rightTrees) { TreeNode curTree = new TreeNode(i); // 创建当前节点 curTree.left = left; curTree.right = right; mList.add(curTree); // 构造一颗新的树添加到集合中。 } } } return mList; }C++：
public:
vector generateTrees (int n) {
return generateTrees(1, n);
}
// 左闭右闭区间[start,end]
vector generateTrees (int start, int end) {
vector
vec; if (start > end) { // 无效区间 vec.push_back( nullptr); return vec; } // 区间继续分成三部分，其中[i]是当前节点，[start, i - 1]是当前节点的所有 // 左子节点，[i + 1, end]是当前节点的所有右子节点，左右子节点继续递归创建。 for ( int i = start; i <= end; i++) { // 递归创建左子树 vector leftTrees = generateTrees(start, i - 1); // 递归创建右子树 vector rightTrees = generateTrees(i + 1, end); // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上 for (TreeNode *left: leftTrees) { for (TreeNode *right: rightTrees) { auto *curTree = new TreeNode(i); // 创建当前节点 curTree->left = left; curTree->right = right; vec.emplace_back(curTree); // 构造一颗新的树添加到集合中。 } } } return vec; }Python：
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def generateTrees(start, end): # 左闭右闭区间[start,end]
trees = []
if start > end: # 无效区间
trees.append(None)
return trees
# 区间继续分成三部分，其中[i]是当前节点，[start, i - 1]是当前节点的所有
# 左子节点，[i + 1, end]是当前节点的所有右子节点，左右子节点继续递归创建。
for i in range(start, end + 1):
left_trees = generateTrees(start, i - 1) # 递归创建左子树
right_trees = generateTrees(i + 1, end) # 递归创建右子树
# 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for left in left_trees:
for right in right_trees:
node = TreeNode(i) # 创建当前节点
node.left = left
node.right = right
trees.append(node) # 构造一颗新的树添加到集合中。
return trees
return generateTrees(1, n)笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴