-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0095.java
49 lines (43 loc) · 1.19 KB
/
Leetcode0095.java
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
47
48
49
package com.y2020.m01.d03;
import com.y2020.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
* Created by zhangweilong on 2020/01/03
*
* @author zhangweilong@corp.netease.com
* @since 2020/01/03
*/
public class Leetcode0095 {
public static void main(String[] args) {
new Leetcode0095().generateTrees(3);
}
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new ArrayList<>();
return dfs(1, n);
}
private List<TreeNode> dfs(int l, int r) {
List<TreeNode> res = new ArrayList<>();
if (l > r) {
res.add(null);
return res;
}
if (l == r) {
res.add(new TreeNode(l));
return res;
}
for (int i = l; i <= r; i++) {
List<TreeNode> left = dfs(l, i - 1);
List<TreeNode> right = dfs(i + 1, r);
for (TreeNode lr : left) {
for (TreeNode rr : right) {
TreeNode treeNode = new TreeNode(i);
treeNode.left = lr;
treeNode.right = rr;
res.add(treeNode);
}
}
}
return res;
}
}