🐰😺🌳 兔猫信奥学院的魔幻树阵探秘 🌳😺🐰

在信奥学院的梦幻果林深处，生长着一株神奇的“排序果树”。加菲老师告诉小兔和小猫：

“给定整数 (n)，我们要用编号 (1) 到 (n) 的果实，恰好生成所有可能的二叉搜索树（BST）形态！每一棵树，都必须满足左子树果实编号小于根，右子树果实编号大于根，而且果实不重复使用。请你们将这些魔法果树一一构造出来，记录下不同结构的所有可能！”

输入格式

输入一行，包含一个整数 n。

• \(1 \le n \le 8\) （由于树的数量随着 Catalan 数快速增长，实际可用性通常在 8 以内）

输出格式

返回所有由 1…n 构成的不同 BST，每棵树按层次遍历（null 用 null 占位）序列化。
可以按任意顺序返回这些序列化结果。

示例 1

3

[
 [1,null,2,null,3],
 [1,null,3,2],
 [2,1,3],
 [3,1,null,null,2],
 [3,2,null,1]
]

对应的 5 种 BST 结构

示例 2

1

[[1]]

🎓 加菲老师寄语：
通过分治+记忆化递归，你可以优雅地构建所有 BST 形态。实践时注意节点回收，以免内存泄露。祝魔幻树阵构建顺利！