leetcode894

 1 class Solution {    
 2     
 3     private Map<Integer, List<TreeNode>> memo;
 4     
 5     public List<TreeNode> allPossibleFBT(int N) {
 6         this.memo = new HashMap<>();
 7         return backtrack(N);
 8     }
 9     
10     private List<TreeNode> backtrack(int n) {
11         List<TreeNode> ret = new ArrayList<>();
12         if (n < 1) {
13             return ret;
14         }
15         
16         if (n == 1) {
17             ret.add(new TreeNode(0));
18             return ret;
19         }
20         
21         if (memo.containsKey(n)) {
22             return memo.get(n);
23         }
24         
25         for (int i = 1; i < n; i++) {
26             for (TreeNode left : backtrack(i)) {
27                 for (TreeNode right : backtrack(n - i - 1)) {
28                     TreeNode node = new TreeNode(0);
29                     node.left = left;
30                     node.right = right;
31                     ret.add(node);
32                 }
33             }
34         }
35         
36         memo.put(n, ret);
37         return ret;
38     }
39 }