P71 - 多路树的内部路径长度

Internal path length of a tree
官方模块：Problems.P71　核心函数：internalPathLength

题目描述

内部路径长度定义为根到每个节点的路径长度之和。根深度为 0，根的孩子深度为 1。

实现

方法一：深度优先递归

1internalPathLength :: MultiwayTree a -> Int
2internalPathLength = go 0
3  where
4    go depth (MultiwayTree _ children) =
5      depth + sum (map (go (depth + 1)) children)

深度作为只读上下文向下传递，当前节点贡献自己的深度，再汇总全部孩子。

方法二：累计子树大小

1internalPathLength :: MultiwayTree a -> Int
2internalPathLength tree = snd (measure tree)
3  where
4    measure (MultiwayTree _ children) =
5      (1 + sum childSizes, sum (zipWith (+) childSizes childPaths))
6      where
7        measuredChildren = map measure children
8        childSizes = map fst measuredChildren
9        childPaths = map snd measuredChildren

每条“父节点到孩子”的边会被孩子子树中的所有节点经过，因此这条边对路径长度总和的贡献等于孩子子树大小。measure 同时返回节点数和内部路径长度，不需要显式传递深度。

方法对比

方法	关键状态
深度优先	从根向下传递当前深度
累计子树大小	从孩子向上返回规模和路径和

测试

1>>> internalPathLength multitree1
20
3>>> internalPathLength multitree5
49
5>>> internalPathLength (MultiwayTree 'a' [MultiwayTree 'b' []])
61

每个节点访问一次，时间复杂度 $O(n)$ ，递归栈深度为树高 $O(h)$ 。

参考

← P70 多路树节点串 | P72 后序遍历 →