LeetCode 894中等树 · BST
所有可能的真二叉树 图解题解
这道题到底在问什么
给一个整数 n，返回所有含 n 个节点的真二叉树（每个节点恰好 0 或 2 个孩子，节点值都为 0）。可按任意顺序返回这些树的根。数据范围 1 ≤ n ≤ 20。
- 输入
- n = 3
- 输出
- [[0,0,0]] 只有 1 棵
- 输入
- n = 7
- 输出
- 5 棵不同形态
先想最直接的笨办法
核心一句话：枚举左子树的奇数节点数，左右各自递归出所有形态，再两两组合。子问题用 f[m] 记下来，不重复算。（动画第 3 步）
最优解：一步一步想明白
- 3核心一句话：枚举左子树的奇数节点数，左右各自递归出所有形态，再两两组合。子问题用 f[m] 记下来，不重复算。
- 4f[1] = 1从最小规模起步。一个节点本身就是一棵合法真二叉树（它没有孩子，满足 0 个孩子的规则）。所以 f[1] 只有这一棵，记进备忘录。
- 5偶数 ⇒ 0 棵为什么后面只算奇数？真二叉树每加一个内部节点就带来两个孩子，节点数永远是「2 乘内部节点数再加 1」，必然是奇数。所以 n=2、4、6 这种偶数，一棵都拼不出来，直接返回空。
- 6左 1 + 右 1n=3 时根占掉 1 个，剩 2 个分给左右。左子树的节点数只能取奇数，唯一选择是左 1、右 1。紫色是左子树（1 个节点），蓝色是右子树（1 个节点）。
- 7f[3] = 1左边拿 f[1] 的那棵（1 棵），右边也拿 f[1] 的那棵（1 棵），1 乘 1 得到这唯一一棵 [0,0,0]。f[3] = 1，写进备忘录。
- 8左 1 + 右 3n=5 第一种拆法：左子树取 1 个节点（紫，来自 f[1]），右子树取 5-1-1=3 个节点（蓝，来自 f[3]）。左边 1 棵、右边 1 棵。
- 91 × 1 = 1 棵左用 f[1] 的 1 棵，右用 f[3] 的 1 棵，组合出 1 棵。这是第一种形态：左边是叶子，右边是个小三角。
- 10左 3 + 右 1n=5 第二种拆法：左子树取 3 个节点（紫，来自 f[3]），右子树取 5-1-3=1 个（蓝，来自 f[1]）。和拆法一左右对调。
- 11f[5] = 2左用 f[3] 的 1 棵、右用 f[1] 的 1 棵，又得 1 棵。两种拆法各贡献 1 棵，f[5] = 1 加 1 = 2，记入备忘录。
- 12f[5] = 2 棵f[5] 一共两棵：一棵左轻右重（左叶子、右三角），一棵左重右轻。它们都会作为「积木」拼进更大的 f[7]，所以现在存好备用。
- 13左 ∈ [1, 3, 5]n=7 时根占 1 个，剩 6 个分左右。左子树的奇数取值有三个：1、3、5，对应右子树 5、3、1。下面逐对组合：[1,5]、[3,3]、[5,1]。
- 141 × 2 = 2第一对：左 1（f[1]=1 棵）、右 5（f[5]=2 棵）。1 乘 2 得 2 棵。先看右子树用 f[5] 的第一种形态。
- 15第 1 棵左边一个叶子，右边接上 f[5] 的「左 1 右 3」那棵，拼成第一棵 7 节点树。
- 16第 2 棵同样左边叶子，右边换成 f[5] 的「左 3 右 1」那棵，得到第二棵。这对总共贡献 2 棵。
- 171 × 1 = 1第二对：左 3（f[3]=1 棵）、右 3（f[3]=1 棵）。1 乘 1 得 1 棵，左右各是一个小三角。
- 18第 3 棵这是最对称的一棵：左右都是 3 节点的小真二叉树，拼成满满的两层。这对贡献 1 棵。
- 192 × 1 = 2第三对：左 5（f[5]=2 棵）、右 1（f[1]=1 棵）。2 乘 1 得 2 棵。左子树先用 f[5] 的第一种。
- 20第 4 棵右边一个叶子，左边接 f[5] 的「左 1 右 3」那棵，得到第四棵。
- 21f[7] = 5右边叶子，左边换成 f[5] 的「左 3 右 1」那棵，第五棵。三对加起来：2 加 1 加 2 = 5，f[7] = 5，正是答案。
- 22自底向上填表回看整张备忘录：f[1]=1、f[3]=1、f[5]=2、f[7]=5。每个规模都是「枚举左子树奇数节点数，左右棵数相乘再求和」算出来的，小的先算、大的复用，一遍填完。
- 23答案 = 5 棵n=7 的所有真二叉树就是 f[7] 里这 5 棵不同形态。把它们的根节点装进列表返回，任务完成。
⚠️ 容易写错的地方
✗ 错：左子树节点数用 +1 递增
✓ 对：必须 +2，只枚举奇数
左右子树各自也得是真二叉树，节点数只能是奇数，步长 1 会造出非法形态
✗ 错：忘了偶数 n 直接返回空
✓ 对：n 为偶数时结果就是空列表
真二叉树节点数恒为奇数，偶数做循环纯属白费且可能出错
✗ 错：不做记忆化
✓ 对：用 f[m] 把每个规模存一次
同一个 f(m) 会被多个上层反复需要，不存就退化成指数级重复递归
完整代码（Python / C++ / Java）
Python
from typing import List, Optional
from functools import cache
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class 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))C++
#include <algorithm>
#include <iostream>
#include <map>
#include <optional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(): val(0), left(nullptr), right(nullptr) {} TreeNode(int x): val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode* l, TreeNode* r): val(x), left(l), right(r) {} };
class Solution {
map<int, vector<TreeNode*>> memo;
public:
vector<TreeNode*> allPossibleFBT(int n) {
if (memo.count(n)) return memo[n];
vector<TreeNode*> ans;
if (n == 1) ans.push_back(new TreeNode(0));
else if (n % 2 == 1) {
for (int l = 1; l < n; l += 2) {
for (auto left : allPossibleFBT(l)) for (auto right : allPossibleFBT(n - 1 - l)) ans.push_back(new TreeNode(0, left, right));
}
}
return memo[n] = ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class Solution {
private Map<Integer, List<TreeNode>> memo = new HashMap<>();
public List<TreeNode> allPossibleFBT(int n) {
if (memo.containsKey(n)) return memo.get(n);
List<TreeNode> ans = new ArrayList<>();
if (n == 1) ans.add(new TreeNode(0));
else if (n % 2 == 1) {
for (int l = 1; l < n; l += 2) {
for (TreeNode left : allPossibleFBT(l)) for (TreeNode right : allPossibleFBT(n - 1 - l)) ans.add(new TreeNode(0, left, right));
}
}
memo.put(n, ans);
return ans;
}
}复杂度
时间
O(Catalan(n))
n 个节点的真二叉树棵数等于第 (n-1)/2 个卡特兰数，结果本身就有这么多棵，逐棵构造无法更快
空间
O(Catalan(n))
备忘录要存下所有规模的全部树，数量级与答案同阶；递归深度只有 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 所有可能的真二叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么一定要记忆化，不记会怎样？+
因为 f(m) 这个子问题会被很多不同的上层组合反复用到（比如算 f[7] 要 f[5]，算 f[9] 也要 f[5]）。不记忆就会一遍遍重算同一个规模，递归树指数级膨胀。存进备忘录后每个规模只算一次，复杂度直接降到答案本身的量级。
不同的大树里，相同的子树会共享同一个对象吗？+
会。参考代码里 f[m] 返回的子树对象会被直接拼进多棵大树，多棵树共享同一份子树引用。因为节点值都是 0、构造过程中从不修改已有节点，这种共享是安全的，还能省下大量内存和构造时间。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 所有可能的真二叉树 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。