leetcode 894 所有可能的满二叉树

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

class Solution:

    def allPossibleFBT(self, N: int) -> List[TreeNode]:
        if N == 1:
            return [TreeNode(0)]
        
        result = []
        for i in range(1, N - 1, 2):
            left = self.allPossibleFBT(i)
            right = self.allPossibleFBT(N - 1 - i)
            for l in left:
                for r in right:
                    head = TreeNode(0)
                    head.left = l
                    head.right = r
                    result.append(head)
        return result