题目：

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.
Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

• 1 <= N <= 20

---

思路：

该题的主要思路是递归。需要找到左子树有几种可能的情况以及右子树有几种可能的情况，详细的说是当左子树的结点数为i时，右子树为N-i时，子树可能出现的几种情况。然后再进行组合。得到结点数为N的情况下可能的子树情况。

---

代码：

public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode>result = new ArrayList<TreeNode>();
        if(N == 0){
            return result;
        }
        if(N == 1){
            TreeNode node = new TreeNode(0);
            result.add(node);
            return result;
        }
        N--;
        for(int i=1;i<=N;i+=2){
            List<TreeNode>L = allPossibleFBT(i);
            List<TreeNode>R = allPossibleFBT(N-i);
            for(TreeNode l:L){
                for(TreeNode r:R){
                    TreeNode node = new TreeNode(0);
                    node.left = l;
                    node.right = r;
                    result.add(node);
                }
            }
        }
        return result;
    }

---

题后思考

做完这道题之后思考了一些。为了能够把这道题给吃透。这道题要的是全二叉子树，就是每个结点要么有两个子节点要么都没有结点。那么可不可把这道题改一下。给定结点的数目求这些结点能够组成的二叉树。其实只需要在原先的代码上稍加改动即可。首先循环需要从0开始，其次得到的左右子树可能有空子树，因此需要分情况讨论，左子树为空，右子树为空，左右子树不空三种情况。

---

代码：

public List<TreeNode> allPossibleTrees(int N){
    List<TreeNode>result = new ArrayList<TreeNode>();
    if(N == 0){
        return result;
    }
    if(N == 1){
        TreeNode node = new TreeNode(0);
        result.add(node);
        return result;
    }
    N--;
    for(int i=0;i<=N;i++){
        List<TreeNode>L = allPossibleTrees(i);
        List<TreeNode>R = allPossibleTrees(N - i);
        if(L.size() == 0){
            for(TreeNode r:R){
                TreeNode node = new TreeNode(0);
                node.right = r;
                result.add(node);
            }
        }else if(R.size() == 0){
            for(TreeNode l:L){
                TreeNode node = new TreeNode(0);
                node.left = l;
                result.add(node);
            }
        }else{
            for(TreeNode l:L){
                for(TreeNode r:R){
                    TreeNode node = new TreeNode(0);
                    node.left = l;
                    node.right = r;
                    result.add(node);
                }
            }
        }
    }
    return result;
}