题目地址(96. 不同的二叉搜索树)
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/
题目描述
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路
这是一个经典的使用分治思路的题目。
对于数字 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):
class Solution: def numTrees(self, n: int) -> int: if n <= 1: return 1 res = 0 for i in range(1, n + 1): res += self.numTrees(i - 1) * self.numTrees(n - i) return res
上面的代码会超时,并没有栈溢出,因此我们考虑使用 hashmap 来优化,代码见下方代码区。
关键点解析
- 分治法
- 笛卡尔积
- 记忆化递归
代码
- 语言支持:Python3
Python3 Code:
class Solution: visited = dict() def numTrees(self, n: int) -> int: if n in self.visited: return self.visited.get(n) if n <= 1: return 1 res = 0 for i in range(1, n + 1): res += self.numTrees(i - 1) * self.numTrees(n - i) self.visited[n] = res return res
相关题目
- 95.unique-binary-search-trees-ii
题目地址(95. 不同的二叉搜索树 II) https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/ 题目描述 给定一个整数 n,生成所有由 1 ... n 为节点所组成的二叉搜索树。 示例: 输入: 3 输出: [ [1,null,3,2], [3,2,n…
LeetCode题解501.Find-Mode-in-Binary-Search-TreeProblem on Leetcode https://leetcode.com/problems/find-mode-in-binary-search-tree/ Description Given a binary search tree (BST) with duplicates, find all the mode(s) (the most freq…
LeetCode题解212.word-search-ii题目地址(212. 单词搜索 II) https://leetcode-cn.com/problems/word-search-ii/description/ 题目描述 给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平…
LeetCode题解145.binary-tree-postorder-traversal题目地址 https://leetcode.com/problems/binary-tree-postorder-traversal/description/ 题目描述 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given bi…
LeetCode题解144.binary-tree-preorder-traversal题目地址 https://leetcode.com/problems/binary-tree-preorder-traversal/description/ 题目描述 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null…