P72 - 多路树的后序遍历
Post-order sequence of a multiway tree
官方模块：
Problems.P72核心函数：postOrderSequence
思路与实现
多路树的后序遍历先依次遍历所有孩子，最后访问根节点。
方法一：concatMap 递归
1postOrderSequence :: MultiwayTree a -> [a]
2postOrderSequence (MultiwayTree x children) =
3 concatMap postOrderSequence children ++ [x]
方法二：累加参数（差异列表）
1postOrderSequence :: MultiwayTree a -> [a]
2postOrderSequence tree = gather tree []
3 where
4 gather (MultiwayTree x children) tail =
5 foldr gather (x : tail) children
gather tree tail 把“遍历结果后面要接的列表”作为参数传入。foldr 保持孩子从左到右的顺序，根节点 x 则放在所有孩子之后。整个过程只使用 (:)，不会反复复制左侧列表。
方法对比
| 方法 | 构造方式 | 复杂度 |
|---|---|---|
concatMap 递归 | 子树结果通过 ++ 拼接 | 偏斜结构可能重复复制 |
| 累加参数 | 直接把结果接到尾参数前 | O(n) |
测试
1>>> postOrderSequence multitree5
2"gfcdeba"
3>>> postOrderSequence (MultiwayTree 1 [])
4[1]