LeetCode 894.所有可能的满二叉树

1.题目

https://leetcode-cn.com/problems/all-possible-full-binary-trees/submissions/

2.题解

这道题的题意很清楚，就是给一个1到20的节点数，给出满足这个节点数的所有满二叉树，用List来返回结果。如果只有一个节点就直接输出唯一一种可能；对于其他情况我的处理方式是采用递归的方法得到结果，具体逻辑是：

首先满二叉树必须同时满足左右子树都是满的才行。（这就可以使用递归）
然后，由于满二叉树都得是奇数，所以我们的最外层for循环才会是int i=1;i+=2;
之后，N个节点，i个在左边子树；自然有N-1-i个在右边子树（1是根节点）；所以下面的递归参数分别是这两个。
最后，我们new一个TreeNode，设置好left和right都是满二叉树的情况，再将这个东西装到List中输出即可。

3.代码

class Solution {
 public List<TreeNode> allPossibleFBT(int N) {
            List<TreeNode> result =new ArrayList<TreeNode>();
            //1
            if(N==1){
                result.add(new TreeNode(0));
                return result;
            }else if(N%2==1) {
                //通常情况
                for (int i = 1; i < N; i += 2) {
                    List<TreeNode> lefts = allPossibleFBT(i);
                    List<TreeNode> rights = allPossibleFBT(N - i-1);
                    for (TreeNode l : lefts)
                        for (TreeNode r : rights) {
                            TreeNode treeNode = new TreeNode(0);
                            treeNode.left = l;
                            treeNode.right = r;
                            result.add(treeNode);
                        }
                }
            }
            return result;

        }
        
    }

4.结果截图