# 0894. All Possible Full Binary Trees
###### tags: `Leetcode` `Medium` `Tree` `Recursion`
Link: https://leetcode.com/problems/all-possible-full-binary-trees/description/
## 思路
backtracking+memo
对于给定的一个n来说 我们遍历所有可能的左半边subtree的node个数
## Code

class Solution {
    Map<Integer, List<TreeNode>> map = new HashMap<>();
    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> list = new ArrayList<>();
        if(map.containsKey(n)) return map.get(n);
        if(n==1){
            list.add(new TreeNode(0));
            map.put(n, list);
            return list;
        }
        for(int left=1; n-left-1>=1; left+=2){
            List<TreeNode> l = allPossibleFBT(left);
            List<TreeNode> r = allPossibleFBT(n-left-1);
            for(int i=0; i<l.size(); i++){
                for(int j=0; j<r.size(); j++){
                    TreeNode root = new TreeNode(0);
                    root.left = l.get(i);
                    root.right = r.get(j);
                    list.add(root);
                }
            }
        }
        map.put(n, list);
        return list;
    }
}