leetcode 95. 不同的二叉搜索树 II
题目：95. 不同的二叉搜索树 II
给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。
示例1:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
提示:
0 <= n <= 8
方法：分治
思路：通过分治的思想，枚举可行根节点将其他元素分为左右子树，左右子树都有可能会有不同的树结构，所以求最终的树结构时，要将左右子树不同树结构相组合，才能得出最终所有树结构。
运行数据：执行用时：2 ms，内存消耗：40.3 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<>();
} else {
return generateTrees(1, n);
}
}
private List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> result = new LinkedList<>();
if (start > end) {
result.add(null);
return result;
}
for (int i = start; i <= end; i++) {
List<TreeNode> leftTrees = generateTrees(start, i - 1);
List<TreeNode> rightTrees = generateTrees(i + 1, end);
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
TreeNode currTree = new TreeNode(i);
currTree.left = leftTree;
currTree.right = rightTree;
result.add(currTree);
}
}
}
return result;
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
