You need to enable JavaScript to run this app. N-ary tree带方向叶到叶路径生成的算法思路咨询
优惠活动
大模型
产品
解决方案
定价
更多

N-ary tree带方向叶到叶路径生成的算法思路咨询

叶到叶路径生成的可落地实现思路

常见认知校准

你之前提到的两个直觉其实不需要严格落地:

  • 没有必要强制使用中序遍历:不管用前序、后序、还是层序遍历,只要能拿到节点和父节点的映射、收集全所有叶子,就能满足计算需求,遍历顺序本身不影响最终路径的正确性
  • 不需要全局保存所有历史访问节点:仅在找两个叶子的最近公共祖先时,临时用一个集合记录上溯路径即可,不需要维护跨整个遍历过程的全局状态

核心实现逻辑

所有叶到叶的路径本质,都是两个不同叶子节点,通过它们的最近公共祖先(LCA)连通形成的唯一路径,只要拆成上溯、下行两段,方向标注自然就出来了,整体分三步:

  1. 一次遍历完成基础信息收集
    从根节点出发遍历整棵树,边遍历边记录两个核心信息:
    • 给每个非根节点,记录它的直接父节点引用,形成「子节点 -> 父节点」的映射表
    • 遇到没有任何子节点的叶子节点,就把它存进全局的叶子列表
  2. 遍历所有不重复的叶子对
    因为树的路径是无向的,所以只要遍历所有无序的叶子对即可,避免同一条路径正着、反着重复输出。对每一对叶子:
    • 从第一个叶子节点出发,顺着父节点链一路往上走到根,把沿途经过的节点全部存下来,同时用一个集合记录这些节点
    • 从第二个叶子节点出发,同样顺着父节点链往上走,第一个碰到的、在刚才的集合里出现过的节点,就是两个叶子的最近公共祖先
    • 从第一个叶子到公共祖先的这段路程,所有移动都是从子节点指向父节点,直接按顺序标UP即可
    • 从公共祖先到第二个叶子的这段路程,把上溯的节点列表反过来就是下行路径,所有移动都是从父节点指向子节点,直接按顺序标DOWN即可
  3. 拼接路径做去重处理
    把两段路径拼起来时,把公共祖先位置重复的节点去掉,就得到了带方向标注的完整叶到叶路径。用你给的示例树验证:叶子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。

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.03 10:15:03