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

按水平链逐行输出¶

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

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

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