# 菱形衣架的排列: 补充解法

## 按水平链逐行输出

Codex（GPT-6）的补充程序 [alternative.cpp](alternative.cpp) 维护当前行若干条水平链的起点。初始只有根。按照起点顺序，沿每条链的右方指针一直走到零，直接输出编号；遇到下方孩子就把它追加到下一行的起点表。当前行结束后换行，并将下一行设为当前行。

归纳不变量：当前起点从左到右排列，每个当前层结点恰好属于其中一条链。下方边使层数加一；[主解的宽度分离证明](solution.zh.md)保证来自较左父亲的下方链整体早于来自较右父亲的下方链，因此按父亲访问顺序收集下一行仍保持左右次序。树无重复父亲，保证没有漏点或重访。根是初始唯一水平链起点，归纳成立。

每个结点只扫描一次，时间 $O(n)$ ；输入树占 $O(n)$ 空间，两个行队列占 $O(w)$ ，其中 $w$ 为最大行宽。此方案可以边生成边输出，适合不需要再次访问已输出行的使用方式。首选深度优先程序保留全部行，适合后续访问行数据。两者均支持完整范围。