LeetCode - 所有可能的满二叉树

LeetCode第894题，难度中等。又是一题突然的100%，虽然并没有达到0ms的地步。

原题地址：https://leetcode-cn.com/problems/all-possible-full-binary-trees/

题目描述：

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

示例：

输入：7

输出：[[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]]

解释：

提示：

1. 1 <= N <= 20

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/all-possible-full-binary-trees

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这题中，我们需要首先搞清楚满二叉树的定义，然后熟练的运用到递归的方式。

这题的解法和之前的求所有子集很像，都是一开始先获取到最小的满二叉树，然后再在这颗满二叉树上面，添加父节点。使得这个树再次满足满二叉树的要求。

由于N为偶数时，不可能有符合要求的满二叉树，所有首先判断N是否是偶数。具体为什么N为偶数时没有满二叉树，各位自己画个图就知道了。

然后如果N为1，那么很明显只有一个节点。

否则的话，就从1到N，每次递加2的方式，分别获取i为3,5....19的情况下的满二叉树子树。当i为3时，左子树节点数量就是3，右子树节点数量就是N-3。分别获取到左右子树后，为左右子树新增一个父节点，然后将该父节点放入当前的List结果集中。

当N为19时，会去分别获取17,15,13....3,1的子树，最后将其组装在一起形成满足条件的满二叉树。

中文官网题解：

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

个人题解：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        if (N % 2 == 0) {
            return new ArrayList<>(0);
        }
        List<TreeNode> list = new ArrayList<>();
        if (N == 1) {
            list.add(new TreeNode(0));
            return list;
        }
        N--;
        for (int i = 1; i < N; i += 2) {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(N - i);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode node = new TreeNode(0);
                    node.left = l;
                    node.right = r;
                    list.add(node);
                }
            }
        }
        return list;
    }
}

结果：

小有实力的选手，居然又是超过了100%。