894. 所有可能的真二叉树

题目描述

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表**。**

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

思路

真二叉树要么没有子节点，要么有两个子节点，意味着整棵树或子树的节点数量一定是奇数。

每增加两个节点，真二叉树会增加一片叶子，因此一共 $n$ 个节点的二叉树一共会有 $\frac{n+1}{2}$ 片叶子。

这样我们可以考虑将返回的真二叉树列表定义为 $f(i)$，其中 $i$ 表示这个二叉树列表有 $i$ 片叶子。

那么左子树有 $j=1,\dots ,i-1$ 片叶子，右子树有 $i-j$ 片叶子。

左子树的所有真二叉树列表为 $f(j)$，右子树的所有真二叉树列表为 $f(i-j)$。这样我们就可以从这两个列表中各选一棵真二叉树作为根节点的左右子树，这样就可以从下到上推导二叉树列表了。

具体到实现上，对于 $i=1$ 的树，它只有一个子节点：

flowchart TD
  A["0"]

接下来处理 $i>1$ 的情况。此时左节点的叶子数量为 $j\in [1,i)$，右节点的叶子数量为 $i-j$，因此接下来我们先枚举 $j$，再给根节点左右子树分配 $f(j)$ 个叶子的子树和 $f(i-j)$ 个叶子的子树即可：

        MAX_TREE = (n+1)//2+1
        f = [[] for _ in range(MAX_TREE)]
        f[1] = [TreeNode(0)]
        for i in range(2, MAX_TREE):
            f[i] = [
                TreeNode(0, left, right)
                for j in range(1, i)
                for left in f[j]
                for right in f[i-j]
            ]

最终代码为：

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []
        MAX_TREE = (n+1)//2+1
        f = [[] for _ in range(MAX_TREE)]
        f[1] = [TreeNode(0)]
        for i in range(2, MAX_TREE):
            f[i] = [
                TreeNode(0, left, right)
                for j in range(1, i)
                for left in f[j]
                for right in f[i-j]
            ]
        return f[MAX_TREE-1]