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
| class Solution {
public List<TreeNode> generateTrees(int n) {
return helper(1, n);
}
private List<TreeNode> helper(int left, int right) {
List<TreeNode> ans = new ArrayList<>();
if (left > right) {
ans.add(null);
return ans;
}
for (int i = left; i <= right; i++) {
List<TreeNode> leftSubList = helper(left, i - 1);
List<TreeNode> rightSubList = helper(i + 1, right);
for (TreeNode leftSub : leftSubList) {
for (TreeNode rightSub : rightSubList) {
TreeNode currRoot = new TreeNode(i);
currRoot.left = leftSub;
currRoot.right = rightSub;
ans.add(currRoot);
}
}
}
return ans;
}
}
|
思路就是轮流让从1到n的值作为root. 假设x作为root, 那么比x小的数字能够组成的BST们就是x的左树, 比x大的数字组成的BST们就是x的右树. 组合就ok了.
时间复杂度和空间复杂度非常难. catlan number好像是.
