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

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

题目描述

1
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
2
3
示例:
4
5
输入: 3
6
输出: 5
7
解释:
8
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
9
10
1 3 3 2 1
11
\ / / / \ \
12
3 2 1 1 3 2
13
/ / \ \
14
2 1 2 3
Copied!

前置知识

  • 二叉搜索树
  • 分治

公司

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

岗位信息

  • 腾讯(广州)- 安卓 - 社招 - 三面

思路

这是一个经典的使用分治思路的题目。
对于数字 n ,我们可以 1- n 这样的离散整数分成左右两部分。我们不妨设其分别为 A 和 B。那么问题转化为 A 和 B 所能组成的 BST 的数量的笛卡尔积。而对于 A 和 B 以及原问题除了规模,没有不同,这不就是分治思路么?至于此,我们只需要考虑边界即可,边界很简单就是 n 小于等于 1 的时候,我们返回 1。
具体来说:
  • 生成一个[1:n + 1] 的数组
  • 我们遍历一次数组,对于每一个数组项,我们执行以下逻辑
  • 对于每一项,我们都假设其是断点。断点左侧的是 A,断点右侧的是 B。
  • 那么 A 就是 i - 1 个数, 那么 B 就是 n - i 个数
  • 我们递归,并将 A 和 B 的结果相乘即可。
其实我们发现,题目的答案只和 n 有关,和具体 n 个数的具体组成,只要是有序数组即可。
题目没有明确 n 的取值范围,我们试一下暴力递归。
代码(Python3):
1
class Solution:
2
def numTrees(self, n: int) -> int:
3
if n <= 1:
4
return 1
5
res = 0
6
for i in range(1, n + 1):
7
res += self.numTrees(i - 1) * self.numTrees(n - i)
8
return res
Copied!
上面的代码会超时,并没有栈溢出,因此我们考虑使用 hashmap 来优化,代码见下方代码区。

关键点解析

  • 分治法
  • 笛卡尔积
  • 记忆化递归

代码

语言支持:Python3, CPP
Python3 Code:
1
class Solution:
2
visited = dict()
3
4
def numTrees(self, n: int) -> int:
5
if n in self.visited:
6
return self.visited.get(n)
7
if n <= 1:
8
return 1
9
res = 0
10
for i in range(1, n + 1):
11
res += self.numTrees(i - 1) * self.numTrees(n - i)
12
self.visited[n] = res
13
return res
Copied!
CPP Code:
1
class Solution {
2
vector<int> visited;
3
int dp(int n) {
4
if (visited[n]) return visited[n];
5
int ans = 0;
6
for (int i = 0; i < n; ++i) ans += dp(i) * dp(n - i - 1);
7
return visited[n] = ans;
8
}
9
public:
10
int numTrees(int n) {
11
visited.assign(n + 1, 0);
12
visited[0] = 1;
13
return dp(n);
14
}
15
};
Copied!
复杂度分析
  • 时间复杂度:一层循环是 N,另外递归深度是 N,因此总的时间复杂度是 $O(N^2)$
  • 空间复杂度:递归的栈深度和 visited 的大小都是 N,因此总的空间复杂度为 $O(N)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。