LeetCode 95.不同的二叉搜索树 II

95. 不同的二叉搜索树 II

95.Unique Binary Search Trees II (Medium)

Leetcode / 力扣

2020-7-26 10:17:45

题目描述

给定一个数字 n,要求生成所有值为 1…n 的二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

解题思路

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
43
44
45
46
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n < 1) return new LinkedList<TreeNode>();
return generateSubTrees(1, n);
}

private List<TreeNode> generateSubTrees(int s, int e){
List<TreeNode> ret = new LinkedList<TreeNode>();
if(s > e){
ret.add(null);
return ret;
}
// 枚举可行根节点
for (int i = s; i <= e; ++i) {
// 获得所有可行的左子树集合
List<TreeNode> leftSubtrees = generateSubTrees(s, i - 1);
// 获得所有可行的右子树集合
List<TreeNode> rightSubtrees = generateSubTrees(i + 1, e);
// 从左子树集合中选出一棵左子树,从右子树集合中选出一棵右子树,拼接到根节点上
for (TreeNode left : leftSubtrees) {
for (TreeNode right : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
ret.add(root);
}
}
}
return ret;
}
}