标题描述
这是 LeetCode 上的 95. 不同的二叉查找树 II ,难度为 中等。
Tag : 「树」、「二叉查找树」、「BST」、「DFS」、「递归」、「爆搜」
给你一个整数 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<=81 <= n <= 8
回溯算法
标题要咱们求一切所能结构的二叉查找树的具体计划,而给定 nn 个节点所能构成的二叉查找树的个数为 卡特兰数。
其他计划数同为卡特兰数的还包含:凸多边形三角划分、n
对括号正确匹配数目 …
回到本题,依据二叉查找查找的特性,若某个子树的根节点为 root
,那么 root
的左子树恣意节点值均比 root.val
要小,root
的右子树恣意节点值均比 root.val
要大。
因此,假设咱们运用 [l,r][l, r] 接连段来结构二叉查找树,并且挑选了节点 t
作为二叉查找树的根节点时,那么运用 [l,t−1][l, t – 1] 结构出来的二叉查找树均可作为根节点 tt 的左子树;同理,运用 [t+1,r][t + 1, r] 结构出来的二叉查找树均可作为根节点 t
的右子树。
也就是说,咱们能够规划递归函数 List<TreeNode> dfs(int l, int r)
,意义为运用接连段 [l,r][l, r] 进行二叉查找树结构,并回来相应调集。
最终答案为 dfs(1, n)
,开始咱们能够枚举 [1,n][1, n] 范围内的的每个数 t
作为根节点,并递归 dfs(l, t - 1)
和 dfs(t + 1, r)
获取左右子树的调集 left
和 right
,结合「乘法原理」,枚举恣意左子树和恣意右子树,即可得到 t
作为根节点的二叉查找树计划集,枚举一切 t
后即可得到一切二叉查找树的总集。
注意:当咱们运用乘法原理,来结构以
t
为根节点的二叉查找树时,其left
或right
某一边可能为空集,但此刻咱们仍要将非空的一边子树进行挂载。
为了保证两层新循环的逻辑会被执行,对于空集咱们不能运用null
来代指,而要运用[null]
来代指。
Java 代码:
class Solution {
public List<TreeNode> generateTrees(int n) {
return dfs(1, n);
}
List<TreeNode> dfs(int l, int r) {
if (l > r) return new ArrayList<>(){{add(null);}};
List<TreeNode> ans = new ArrayList<>();
for (int i = l; i <= r; i++) {
for (TreeNode x : dfs(l, i - 1)) {
for (TreeNode y : dfs(i + 1, r)) {
TreeNode root = new TreeNode(i);
root.left = x; root.right = y;
ans.add(root);
}
}
}
return ans;
}
}
TypeScript 代码:
function generateTrees(n: number): Array<TreeNode | null> {
function dfs(l: number, r: number): Array<TreeNode | null> {
if (l > r) return [null]
const ans = new Array<TreeNode>()
for (let i = l; i <= r; i++) {
for (const x of dfs(l, i - 1)) {
for (const y of dfs(i + 1, r)) {
const root = new TreeNode(i)
root.left = x; root.right = y
ans.push(root)
}
}
}
return ans
}
return dfs(1, n)
}
Python 代码:
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def dfs(l, r):
if l > r:
return [None]
ans = []
for i in range(l, r + 1):
for x in dfs(l, i - 1):
for y in dfs(i + 1, r):
root = TreeNode(i)
root.left, root.right = x, y
ans.append(root)
return ans
return dfs(1, n)
- 时刻复杂度:卡特兰数
- 空间复杂度:卡特兰数
最后
这是咱们「刷穿 LeetCode」系列文章的第 No.95
篇,系列开始于 2021/01/01,截止于开始日 LeetCode 上共有 1916 道标题,部分是有锁题,咱们将先把一切不带锁的标题刷完。
在这个系列文章里边,除了解说解题思路以外,还会尽可能给出最为简练的代码。如果涉及通解还会相应的代码模板。
为了便利各位同学能够电脑上进行调试和提交代码,我建立了相关的库房:github.com/SharingSour… 。
在库房地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「书面考试/面试」相关资料可拜访排版精美的 合集新基地 🎉🎉