如何移除元组列表表示的树结构中的直链中间节点

问题说明 #

我们采用(父节点, 子节点)格式的元组列表表示树结构，示例输入如下：
[(0,1), (0,2), (0,3), (1,4), (1,5), (2,6), (6,7), (7,8)]
从元组列表可以还原出完整树结构：

• 节点0共有3个子节点，分别是1、2、3
• 节点1共有2个子节点，分别是4、5
• 节点2仅1个子节点6，节点6仅1个子节点7，节点7仅1个子节点8

其中路径0 -> 2 -> 6 -> 7 -> 8是一条全程没有分叉的直链，按照处理规则，这类直链上的所有中间节点（即2、6、7）都要移除，直接让直链最顶端的分叉节点和最末端的节点建立连接。
通用处理规则：只要两个节点之间的路径上，所有中间节点都只有1个子节点（即路径上不存在分叉），就跳过全部中间节点，直接连接路径两端的节点。比如节点1和它的子节点之间如果夹了若干个只有单个子节点的中间节点，也需要跳过这些中间节点，直接建立上层节点和末端子节点的连接。

预期输出 #

上述示例输入经过处理后，最终输出的边列表为：
[(0,1), (0,8), (0,3), (1,4), (1,5)]

实现逻辑参考 #

• 首先遍历所有原始边，构建「节点-对应子节点列表」的映射表，方便快速查询任意节点的子节点数量
• 逐一遍历每条原始边，从边对应的子节点开始向下追溯：只要当前追溯到的节点有且仅有1个子节点，就继续向下遍历，直到走到叶子节点（没有子节点），或是遇到拥有多个子节点的分叉点时停止
• 将原始边的父节点和追溯到的末端节点组合为新边，对所有新边去重后，就是压缩完成的最终结果

内容的提问来源于stack exchange，提问作者Ghulam Usman