N-ary tree带方向叶到叶路径生成的算法思路咨询
叶到叶路径生成的可落地实现思路
常见认知校准
你之前提到的两个直觉其实不需要严格落地:
- 没有必要强制使用中序遍历:不管用前序、后序、还是层序遍历,只要能拿到节点和父节点的映射、收集全所有叶子,就能满足计算需求,遍历顺序本身不影响最终路径的正确性
- 不需要全局保存所有历史访问节点:仅在找两个叶子的最近公共祖先时,临时用一个集合记录上溯路径即可,不需要维护跨整个遍历过程的全局状态
核心实现逻辑
所有叶到叶的路径本质,都是两个不同叶子节点,通过它们的最近公共祖先(LCA)连通形成的唯一路径,只要拆成上溯、下行两段,方向标注自然就出来了,整体分三步:
- 一次遍历完成基础信息收集
从根节点出发遍历整棵树,边遍历边记录两个核心信息:- 给每个非根节点,记录它的直接父节点引用,形成「子节点 -> 父节点」的映射表
- 遇到没有任何子节点的叶子节点,就把它存进全局的叶子列表
- 遍历所有不重复的叶子对
因为树的路径是无向的,所以只要遍历所有无序的叶子对即可,避免同一条路径正着、反着重复输出。对每一对叶子:- 从第一个叶子节点出发,顺着父节点链一路往上走到根,把沿途经过的节点全部存下来,同时用一个集合记录这些节点
- 从第二个叶子节点出发,同样顺着父节点链往上走,第一个碰到的、在刚才的集合里出现过的节点,就是两个叶子的最近公共祖先
- 从第一个叶子到公共祖先的这段路程,所有移动都是从子节点指向父节点,直接按顺序标
UP即可 - 从公共祖先到第二个叶子的这段路程,把上溯的节点列表反过来就是下行路径,所有移动都是从父节点指向子节点,直接按顺序标
DOWN即可
- 拼接路径做去重处理
把两段路径拼起来时,把公共祖先位置重复的节点去掉,就得到了带方向标注的完整叶到叶路径。用你给的示例树验证:叶子5和叶子4的公共祖先是2,上溯段是5→3→2(对应5 UP 3 UP 2),下行段是2→4(对应2 DOWN 4),去掉重复的2之后就是题目给出的第一条示例路径。
可参考的伪代码流程
# 初始化基础数据 parent_map = 空字典 leaf_list = 空列表 # 第一步:遍历整棵树收集信息 从根节点开始递归/迭代遍历: 对当前遍历到的子节点child,以及它的父节点parent: 如果child没有任何子节点: 把child加入leaf_list 在parent_map中记录 child: parent 的映射 # 第二步:遍历所有叶子对生成路径 result = 空列表 for i 从0到len(leaf_list)-1: for j 从i+1到len(leaf_list)-1: leaf_a = leaf_list[i] leaf_b = leaf_list[j] # 构造a到根的上溯路径 up_path_a = [] visited = 空集合 curr = leaf_a while curr 存在父节点: up_path_a.append(curr) visited.add(curr) curr = parent_map[curr] up_path_a.append(curr) # 把根节点加进去 # 找a和b的公共祖先 curr = leaf_b down_to_b = [] while curr 不在 visited中: down_to_b.append(curr) curr = parent_map[curr] lca = curr # 拼接成带方向的路径文本 path_text = "" # 处理a到LCA的UP段 for 相邻节点对 (child_node, parent_node) 遍历up_path_a的相邻对: path_text += f"{child_node} UP {parent_node} " # 去掉末尾多余的LCA,处理b从LCA来的DOWN段 path_text = path_text.rstrip(f"{lca} ") for 相邻节点对 (parent_node, child_node) 遍历down_to_b的反向相邻对: path_text += f"DOWN {child_node} " # 把最终文本加入结果 result.append(path_text.strip()) 返回result
注:这个算法的时间复杂度和树的高度、叶子总数相关,没有额外引入复杂的遍历流程,对N-ary树完全通用,不需要针对不同分支数做特殊适配。
内容的提问来源于stack exchange,提问作者Exploring。
相关产品推荐
相关产品推荐

