题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

满二叉树是一类二叉树，其中每个结点恰好有 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 <= N <= 20

解答

做这道题，几个基础知识需要留意：

满二叉树是每个结点有0或2个子节点的树；
满二叉树中的结点个数一定为奇数，这是由于根节点的存在造成的；
满二叉树中的所有子树均为满二叉树。

根据以上三个原则，我们可以构造给定结点数的所有满二叉树。

树的构造常常用递归实现，经典的递归函数中的各个功能块的顺序为：终止条件及其返回值；递归操作及其返回值，递归函数内部常常使用循环的方式调用自身，以达到考虑各种情况的目的，尤其在回溯算法中常用。接下来是针对这道题目的递归函数的编排方式：

函数入口处，判断终止条件，即所要求的结点数为1时，这时可以构成满二叉树，而且这个满二叉树其实只有一个根节点，直接返回一棵只有一个结点的树即可；
特殊情况的判断，因为我们已经知道，满二叉树一定含有奇数个结点，因此对于N为偶数的情况，无法构成满二叉树，直接返回一个空列表即可；
其他更加普遍的情况，一棵拥有N个结点的满二叉树，根节点占用了1个，剩下N-1个结点分配给左子树和右子树，为了考虑全面，我们将左子树中结点数目从1开始，一直到N-1，步长为2（因为如果希望左子树为满二叉树，其分配的结点数一定是奇数），相应的，右子树分配得到的结点数为N-1-左子树的结点数。

我们用while来控制使所有划分方式合法。

对于每一种划分方式，通过对函数递归调用，都可以获得若干满左子树和满右子树，我们要考虑的，正是将这些情况进行组合，构造二叉树的规则比较固定了：实例化根节点，添加左子树，添加右子树，最后将这棵含有N个结点的满二叉树添加到结果列表res中。

以上操作完成后，需要及时将左子树和右子树中的结点数更新，以实现新的划分方式。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def allPossibleFBT(self, N: int):
        if N == 1:
            return [TreeNode(0)]

        if N % 2 == 0:
            return []
        left_num, right_num = 1, N - 2

        res = []
        while right_num > 0:
            for left_tree in self.allPossibleFBT(left_num):
                for right_tree in self.allPossibleFBT(right_num):
                    root = TreeNode(0)
                    root.left = left_tree
                    root.right = right_tree
                    res.append(root)
            left_num += 2
            right_num -= 2

        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析