所有可能的真二叉树

这个题解使用了动态规划的思想。首先，它初始化了一个列表 `f`，其中 `f[i]` 用于存储所有包含 `i` 个节点的真二叉树的根节点。由于真二叉树的节点数必须是奇数（除了根节点外，每两个子节点加一个节点），因此只需要计算奇数个节点的情形。对于每个奇数 `i`，遍历所有可能的左子树大小 `left_size`（也必须是奇数），然后对于每个 `left_size`，通过 `product` 函数从 `f[left_size]` 和 `f[i - 1 - left_size]` 中取出所有可能的左、右子树组合，为每对左右子树创建一个新的根节点，最后将这些树根节点存储在 `f[i]` 中。`product` 是笛卡尔积，用于生成所有可能的左右子树组合。

时间复杂度: O(4^n / n^(3/2))

空间复杂度: O(4^n / n^(3/2))

# https://space.bilibili.com/206214
f = [[] for _ in range(21)] # 初始化存储各个节点数的真二叉树列表
f[1] = [TreeNode(0)] # 只有一个节点时，只有一棵树: 只有根节点
for i in range(3, 21, 2): # 只考虑奇数个节点的情况
    f[i] = [TreeNode(0, left, right) # 为每种左右子树组合创建新的树根节点
            for left_size in range(1, i, 2) # 遍历所有可能的左子树大小
            for left, right in product(f[left_size], f[i - 1 - left_size])] # 从可能的左右子树中生成所有组合

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]: # 返回包含n个节点的所有可能的真二叉树
        return f[n] # 直接返回预计算结果