1
/**
2
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
3
 * right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left,
4
 * TreeNode right) { this.val = val; this.left = left; this.right = right; } }
5
 */
6
class Solution {
7
  public List<TreeNode> generateTrees(int n) {
8
    return helper(1, n);
9
  }
10

11
  public List<TreeNode> helper(int lo, int hi) {
12
    List<TreeNode> res = new ArrayList<>();
13
    if (lo > hi) {
14
      res.add(null);
15
      return res;
16
    }
17

18
    for (int i = lo; i <= hi; i++) {
19
      List<TreeNode> left = helper(lo, i - 1);
20
      List<TreeNode> right = helper(i + 1, hi);
21

22
      for (TreeNode l : left) {
23
        for (TreeNode r : right) {
24
          TreeNode head = new TreeNode(i);
25
          head.left = l;
26
          head.right = r;
27

28
          res.add(head);
29
        }
30
      }
31
    }
32

33
    return res;
34
  }
35
}