class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
ArrayList<TreeNode> res = new ArrayList<>();
return res;
}
return generateTrees(1,n);
}
private ArrayList<TreeNode> generateTrees(int left, int right) {
ArrayList<TreeNode> res = new ArrayList<>();
if (left > right) {
res.add(null);
return res;
}
for (int i = left; i <= right; i++) {
ArrayList<TreeNode> lefts = generateTrees(left, i - 1);//以i作为根节点，左子树由[1,i-1]构成
ArrayList<TreeNode> rights = generateTrees(i + 1, right);//右子树由[i+1, n]构成
for (int j = 0; j < lefts.size(); j++) {
for (int k = 0; k < rights.size(); k++) {
TreeNode root = new TreeNode(i);
root.left = lefts.get(j);
root.right = rights.get(k);
res.add(root);
}
}
}
return res;
}
}
