0894：所有可能的真二叉树（1784 分）

力扣第 99 场周赛第 3 题

题目

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

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

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

示例 1：

输入：n = 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]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

• 1 <= n <= 20

分析

按左右子树分别有多少个节点，可以转为递归子问题。 最简单的子问题即是 n=1，只有根节点。

注意满二叉树的节点数必然是奇数，可以节省时间。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def allPossibleFBT(self, n: int) -> List[TreeNode]:
    if n % 2 == 0:
        return []
    if n == 1:
        return [TreeNode(0)]
    res = []
    for i in range(1, n-1, 2):
        for left in self.allPossibleFBT(i):
            for right in self.allPossibleFBT(n-1-i):
                res.append(TreeNode(0, left, right))
    return res

128 ms