第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0095. 不同的二叉搜索树 II

题目地址(95. 不同的二叉搜索树 II)

题目描述

1
给定一个整数 n,生成所有由 1 ... n 为节点所组成的二叉搜索树。
2
3
示例:
4
5
输入: 3
6
输出:
7
[
8
[1,null,3,2],
9
[3,2,null,1],
10
[3,1,null,null,2],
11
[2,1,3],
12
[1,null,2,null,3]
13
]
14
解释:
15
以上的输出对应以下 5 种不同结构的二叉搜索树:
16
17
1 3 3 2 1
18
\ / / / \ \
19
3 2 1 1 3 2
20
/ / \ \
21
2 1 2 3
Copied!

前置知识

  • 二叉搜索树
  • 分治

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一个经典的使用分治思路的题目。基本思路和96.unique-binary-search-trees一样。
只是我们需要求解的不仅仅是数字,而是要求解所有的组合。我们假设问题 f(1, n) 是求解 1 到 n(两端包含)的所有二叉树。那么我们的目标就是求解 f(1, n)。
我们将问题进一步划分为子问题,假如左侧和右侧的树分别求好了,我们是不是只要运用组合的原理,将左右两者进行合并就好了,我们需要两层循环来完成这个过程。

关键点解析

  • 分治法

代码

语言支持:Python3, CPP
Python3 Code:
1
class Solution:
2
def generateTrees(self, n: int) -> List[TreeNode]:
3
if not n:
4
return []
5
6
def generateTree(start, end):
7
if start > end:
8
return [None]
9
res = []
10
for i in range(start, end + 1):
11
ls = generateTree(start, i - 1)
12
rs = generateTree(i + 1, end)
13
for l in ls:
14
for r in rs:
15
node = TreeNode(i)
16
node.left = l
17
node.right = r
18
res.append(node)
19
20
return res
21
22
return generateTree(1, n)
Copied!
CPP Code:
1
class Solution {
2
private:
3
vector<TreeNode*> generateTrees(int first, int last) {
4
if (first > last) return { NULL };
5
vector<TreeNode*> v;
6
for (int i = first; i <= last; ++i) {
7
auto lefts = generateTrees(first, i - 1);
8
auto rights = generateTrees(i + 1, last);
9
for (auto left : lefts) {
10
for (auto right : rights) {
11
v.push_back(new TreeNode(i));
12
v.back()->left = left;
13
v.back()->right = right;
14
}
15
}
16
}
17
return v;
18
}
19
public:
20
vector<TreeNode*> generateTrees(int n) {
21
if (n <= 0) return {};
22
return generateTrees(1, n);
23
}
24
};
Copied!
复杂度分析 令 C(N) 为 N 的卡特兰数。
  • 时间复杂度:$O(N*C(N))$
  • 空间复杂度:$O(C(N))$

相关题目