返回嵌套集合中对象的最大深度（JavaScript）

Question

我正在寻找一种合适的算法，该算法将返回集合层次结构中对象集合的最大深度。我有一个根对象，它可能包含也可能不包含相同类型、数量可变的对象的集合。这些子对象中的每一个本身都可以包含相同类型和可变数量的集合，依此类推，直至任何深度。 （见图）。

我正在寻找最好的算法，该算法将返回一个整数，该整数表示层次结构中最深集合的级别。 （所以在我的图中，这将是 4。）。

我已经递归地尝试了以下函数，但它总是落后一。

 var getLevelFunc = function (children) {
             var depth = 0
            for (var c = 0; c < children.length; c++) {
                let child= children[c];
                if (child.children() != null && child.children().length > 0) {
                    var tempDepth = getLevelFunc(child.children());
                    if (tempDepth > depth) {
                        depth = tempDepth
                    }
                }
            }
            return 1 + depth;
        }

非常感谢

Answer 1

我不是 100% 确定你所拥有的数据结构，所以我嘲笑了一个更简单的数据结构，没有任何

children()

方法，但希望它仍然有意义。

我认为让你的解决方案有点棘手的部分原因是你从子节点而不是节点开始，毕竟如果你有一个没有子节点的节点，它的深度应该仍然为一（如果我理解正确的话） ）。通过在每个阶段将深度传递到

getLevelFunc

，我认为这可能会让您更容易看到代码中应该发生什么。

const tree = {
  name: 'root',
  children: [
    {
      name: 'Child 1',
      children: [
        { name: 'Child 1.1' },
        {
          name: 'Child 1.2',
          children: [
            { name: 'Child 1.2.1' },
            { name: 'Child 1.2.2' },
            { name: 'Child 1.2.3' },
          ]
        }
      ],
    },
    {
      name: 'Child 2',
      children: [
        { name: 'Child 2.1' },
        { name: 'Child 2.2' },
      ],
    },
    { name: 'Child 3' },
  ]
};

const getLevelFunc = function (node, start_depth = 1) {
  let depth = start_depth;
  
  for (const child of (node.children ?? []))
    depth = Math.max(depth, getLevelFunc(child, start_depth + 1));
  
  return depth;
};

console.log(getLevelFunc(tree));

Answer 2

如果您熟悉 @ut8pia/classifier 库，您会认为这是“搜索和选择”模式解决的常见场景。从这个角度来看树的最大深度的计算揭示了它本质上等同于计算根节点的所有后代。因此，在代码中反映这种等价性在概念上更合理。我强烈建议通过采用统一的模式来解决问题，而不是创建特定的函数。

import { ArrayQueue } from "@ut8pia/classifier/queue/ArrayQueue.js";
import {Path} from "@ut8pia/fluent/util/Path.js";
import assert from "assert";

   const root = {
        name: 'root',
        children: [
            {name: 'Child 1',
            children: [
                { name: 'Child 1.1', children: [] },
                { name: 'Child 1.2', children: [
                    { name: 'Child 1.2.1', children: [] },
                    { name: 'Child 1.2.2', children: [] },
                    { name: 'Child 1.2.3', children: [] }
                ]}
            ]},
            {name: 'Child 2', children: [
                { name: 'Child 2.1', children: [] },
                { name: 'Child 2.2', children: [] },
            ]},
            { name: 'Child 3', children: [] }
        ]},

        n = 11,

        depth = 4;

此模式利用

Queue

作为堆栈来探索

search space

。这个空间是一个函数，提供与每个探索点相对应的相邻点。

例如，当探索根节点的所有后代时，该点代表节点本身，

search space

由函数

node => node.children

定义。

const
    search = new ArrayQueue()
        .let(root)
            .search(node => node.children)  

为了计算最大深度，该点指的是

Path

节点，并且空间由将路径延伸到最后一个节点的所有子节点的函数定义：

path => path.across(path.last.children)

。

const
    search = new ArrayQueue()
        .let(Path.of(root))
            .search(path => path.across(path.last.children)),
    got = search
        .toArray()
            .map(path => path.length)
                .reduce((a, b) => Math.max(a, b))

search

实例属于一个可迭代类，它提供了缩小

search

范围、将其与其他迭代相结合或修改它的方法。例如，

toArray()

方法将搜索转换为数组。

您可以通过以下方式验证建议的解决方案：

assert.equal(search.toArray().length, n);
assert.equal(got, depth)