时间戳

首页 > 解决方案 > 给定一个类似“树”的数据结构，打印出从叶子到根的所有路径

computer-science - 给定一个类似“树”的数据结构，打印出从叶子到根的所有路径

问题描述

有人可以指导我正确的方向吗，我不明白如何将结果从叶子返回到根

tree = {
    "name": "root",
    "children": [
        {
            "name": "child1",
            "children": [
                {
                    "name": "grand_child1",
                    "children": []
                },
                {
                    "name": "grand_child2",
                    "children": []
                }
            ]
        },
        {
            "name": "child2",
            "children": []
        }
    ]
}

编辑：解决方案应该是一种算法，因为如果树深度增加它应该仍然有效

标签： computer-science

解决方案

您可以使用递归，例如：

def traverse(node, *names, &block)
  names.unshift(node[:name])

  yield *names and return if node[:children].empty?

  node[:children].each { |child| traverse(child, *names, &block) }
end

该方法在单个节点上运行。在每次调用时，它将节点的名称添加到聚集列表names（最初为空）。然后它为每个孩子再次调用自己，通过names. 如果一个节点没有任何子节点，它将屈服于names给定的块。（这也被传递）

用法：

traverse(tree) do |*names|
  p name: names
end

输出：

{:name=>["grand_child1", "child1", "root"]}
{:name=>["grand_child2", "child1", "root"]}
{:name=>["child2", "root"]}

推荐阅读