所有可能的真二叉树

核心一句话：枚举左子树的奇数节点数，左右各自递归出所有形态，再两两组合。子问题用 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 是第一个非平凡情形。

面试重点：讲清记忆化为什么必要，以及子树对象被多棵树安全共享。