All Possible Full Binary Trees LeetCode solution in Java

1
class Solution {
2
  List<TreeNode>[] memo;
3

4
  public List<TreeNode> allPossibleFBT(int n) {
5
    memo = new ArrayList[n + 1];
6
    return dp(n);
7
  }
8

9
  public List<TreeNode> dp(int n) {
10
    if (n == 0 || n == 2) {
11
      return new ArrayList<TreeNode>();
12
    }
13
    if (n == 1) {
14
      List<TreeNode> temp = new ArrayList<>();
15
      temp.add(new TreeNode(0));
16
      return temp;
17
    }
18
    List<TreeNode> res = new ArrayList<>();
19
    for (int i = 1; i < n - 1; i = i + 2) {
20
      List<TreeNode> right;
21
      List<TreeNode> left;
22
      if (memo[i] != null) right = memo[i];
23
      else right = dp(i);
24
      if (memo[n - 1 - i] != null) left = memo[n - 1 - i];
25
      else left = dp(n - 1 - i);
26

27
      for (TreeNode l : left) {
28
        for (TreeNode r : right) {
29
          TreeNode temp = new TreeNode(0);
30
          temp.left = l;
31
          temp.right = r;
32
          res.add(temp);
33
        }
34
      }
35
    }
36
    memo[n] = res;
37
    return res;
38
  }
39
}