题目描述
思路解析
一句话答案：LeetCode 894 所有可能的真二叉树：n 为偶数一棵都拼不出，dfs(m) 按左子树的奇数节点数分治、左右形态两两组合拼根，记忆化复用子问题避免重算，时间 O(卡特兰数)。
n 个节点能摆出哪些真二叉树
给一个整数 n，要列出所有恰好 n 个节点的真二叉树，也就是每个节点要么没有孩子、要么正好挂两个孩子，绝不只带一个。节点值全是 0，真正要区分的只有形状。题面里 n=3 只有一棵，根挂两个叶子，记作 [0,0,0]；n=7 能拼出 5 棵不同形态，都要返回。
想把节点硬摆成合法形状，为什么越摆越乱
真二叉树没有现成的形态清单可查。盯着 n 个节点硬凑，这里补个孩子、那里又剩一个单挂的不合法，合法与非法的半成品搅在一起，越摆越乱，手摆既漏又重。
根一拆两半，节点数为什么只能是奇数
换成从根往下拆就顺了。任何真二叉树的根都带着左右两棵子树，这两棵各自也是真二叉树。于是一棵 m 个节点的真二叉树，就是「根 1 个 + 左子树 + 右子树」，左右节点数加起来正好 m−1。
关键约束是：真二叉树的节点数必为奇数。除根之外每加一个带孩子的节点就一次多两个孩子，总数永远是「2 乘内部节点数再加 1」，逢偶数一棵都拼不出。既然左右子树也是真二叉树，它们的节点数就只能取奇数：左子树取 1、3、5，右子树对应 m−2、m−4、m−6。按左子树大小把大问题拆成一组组小问题，正是分治。
dfs(m) 每次返回什么，f[m] 又存了什么
写成函数 dfs(m)，它返回的不是数量，而是 m 个节点能拼出的每一棵真二叉树。m=1 是递归出口，单独一个节点自己就是合法的真二叉树，返回它。m 是别的奇数时，让左子树大小 left_size 从 1 起、每次加 2，右子树就是 m−1−left_size。
对每个 left_size，先递归拿到左子树的全部形态、再拿到右子树的全部形态，左边每棵配右边每棵各拼一个新根收进答案。同一规模会被反复用到——算 f[7] 要 f[5]，算 f[9] 还要 f[5]。于是记忆化：dfs(m) 第一次的结果按 m 存进 f[m]，算过就不再重算。
n=7 的 5 棵，是怎么乘出来又加起来的
这里 f[m] 记的是棵数——即 dfs(m) 返回的树的个数，左右棵数相乘就是两两搭配的组合数。从最小的填起。f[1]=1，就是单个叶子。f[3]：左只能取 1、右取 3−1−1=1，相乘得 1，f[3]=1。f[5]：左取 1 时右是 3，f[1]×f[3]=1；左取 3 时右是 1，f[3]×f[1]=1；两拆法相加得 f[5]=2。
轮到 f[7]，根占 1、剩 6 个分左右，左子树取 1、3、5。左 1 右 5：f[1]×f[5]=1×2=2；左 3 右 3：f[3]×f[3]=1；左 5 右 1：f[5]×f[1]=2×1=2。三种相加 2+1+2=5，正是题面的 5 棵。
答案有多少棵，就得老实造多少棵
n 个节点的真二叉树棵数等于卡特兰数：n=5 是 2、n=7 是 5、n=9 是 14。答案本身就这么多棵，逐棵构造省不掉，时间和空间都是 O(卡特兰数)，递归深度只有 O(n)。偶数 n 一棵合法树都拼不出，直接返回空列表；left_size 步长写成加 1 就会造出节点数为偶的非法子树，必须加 2 只取奇数；记忆化更省不得，漏了它同一规模反复重造，递归指数级膨胀。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句话：枚举左子树的奇数节点数，左右各自递归出所有形态，再两两组合。子问题用 f[m] 记下来，不重复算。
f[1] · 最小的真二叉树：从最小规模起步。一个节点本身就是一棵合法真二叉树（它没有孩子，满足 0 个孩子的规则）。所以 f[1] 只有这一棵，记进备忘录。
关键洞察 · 节点数必为奇数：为什么后面只算奇数？真二叉树每加一个内部节点就带来两个孩子，节点数永远是「2 乘内部节点数再加 1」，必然是奇数。所以 n=2、4、6 这种偶数，一棵都拼不出来，直接返回空。
f[3] · 唯一拆法：n=3 时根占掉 1 个，剩 2 个分给左右。左子树的节点数只能取奇数，唯一选择是左 1、右 1。紫色是左子树（1 个节点），蓝色是右子树（1 个节点）。
f[3] · 组合完成：左边拿 f[1] 的那棵（1 棵），右边也拿 f[1] 的那棵（1 棵），1 乘 1 得到这唯一一棵 [0,0,0]。f[3] = 1，写进备忘录。
f[5] · 拆法一：n=5 第一种拆法：左子树取 1 个节点（紫，来自 f[1]），右子树取 5-1-1=3 个节点（蓝，来自 f[3]）。左边 1 棵、右边 1 棵。
f[5] · 拆法一完成：左用 f[1] 的 1 棵，右用 f[3] 的 1 棵，组合出 1 棵。这是第一种形态：左边是叶子，右边是个小三角。
f[5] · 拆法二：n=5 第二种拆法：左子树取 3 个节点（紫，来自 f[3]），右子树取 5-1-3=1 个（蓝，来自 f[1]）。和拆法一左右对调。
f[5] · 拆法二完成：左用 f[3] 的 1 棵、右用 f[1] 的 1 棵，又得 1 棵。两种拆法各贡献 1 棵，f[5] = 1 加 1 = 2，记入备忘录。
f[5] · 两种形态汇总：f[5] 一共两棵：一棵左轻右重（左叶子、右三角），一棵左重右轻。它们都会作为「积木」拼进更大的 f[7]，所以现在存好备用。
f[7] · 枚举左子树节点数：n=7 时根占 1 个，剩 6 个分左右。左子树的奇数取值有三个：1、3、5，对应右子树 5、3、1。下面逐对组合：[1,5]、[3,3]、[5,1]。
f[7] · 左 1 + 右 5：第一对：左 1（f[1]=1 棵）、右 5（f[5]=2 棵）。1 乘 2 得 2 棵。先看右子树用 f[5] 的第一种形态。
f[7] · 左 1 右 5 之一：左边一个叶子，右边接上 f[5] 的「左 1 右 3」那棵，拼成第一棵 7 节点树。
f[7] · 左 1 右 5 之二：同样左边叶子，右边换成 f[5] 的「左 3 右 1」那棵，得到第二棵。这对总共贡献 2 棵。
f[7] · 左 3 + 右 3：第二对：左 3（f[3]=1 棵）、右 3（f[3]=1 棵）。1 乘 1 得 1 棵，左右各是一个小三角。
f[7] · 左 3 右 3 完成：这是最对称的一棵：左右都是 3 节点的小真二叉树，拼成满满的两层。这对贡献 1 棵。
f[7] · 左 5 + 右 1：第三对：左 5（f[5]=2 棵）、右 1（f[1]=1 棵）。2 乘 1 得 2 棵。左子树先用 f[5] 的第一种。
f[7] · 左 5 右 1 之一：右边一个叶子，左边接 f[5] 的「左 1 右 3」那棵，得到第四棵。
f[7] · 左 5 右 1 之二：右边叶子，左边换成 f[5] 的「左 3 右 1」那棵，第五棵。三对加起来：2 加 1 加 2 = 5，f[7] = 5，正是答案。
备忘录回放：回看整张备忘录：f[1]=1、f[3]=1、f[5]=2、f[7]=5。每个规模都是「枚举左子树奇数节点数，左右棵数相乘再求和」算出来的，小的先算、大的复用，一遍填完。
完成 · 收集答案：n=7 的所有真二叉树就是 f[7] 里这 5 棵不同形态。把它们的根节点装进列表返回，任务完成。
边界先想清：n=1 是递归出口，偶数全返回空，n=3 是第一个非平凡情形。
面试重点：讲清记忆化为什么必要，以及子树对象被多棵树安全共享。
参考代码
from typing import List, Optionalfrom functools import cacheclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]: @cache def dfs(m): if m == 1: return [TreeNode(0)] ans = [] if m % 2 == 1: for left_size in range(1, m, 2): for left in dfs(left_size): for right in dfs(m - 1 - left_size): ans.append(TreeNode(0, left, right)) return ans return list(dfs(n))复杂度
- 时间：O(Catalan(n))，n 个节点的真二叉树棵数等于第 (n-1)/2 个卡特兰数，结果本身就有这么多棵，逐棵构造无法更快
- 空间：O(Catalan(n))，备忘录要存下所有规模的全部树，数量级与答案同阶；递归深度只有 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么一定要记忆化，不记会怎样？
追问不同的大树里，相同的子树会共享同一个对象吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
翻转等价二叉树
LeetCode 951 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题