英文:
Return the Maximum Depth of objects in a Nested Collection (JavaScript)
问题
我正在寻找一个合适的算法，它将返回在一个嵌套的对象集合层次结构中对象的最大深度。我有一个根对象，该对象可能包含一个或多个相同类型的对象集合，数量不定。每个子对象本身也可能包含一个相同类型和数量不定的集合，以此类推，直到任意深度（见图表）。
我正在寻找一个最佳算法，该算法将返回一个整数，表示层次结构中最深集合的级别（在我的图表中是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;
}
非常感谢。
英文:
I looking for a suitable algorithm that will return the maximum depth of a collection of objects within a hierarchy of collections. I have a root object which may or may not contain a collection of objects of the same type, of variable number. Each of these child objects, themselves may contain a collection of the same type and variable number, and so-on, down to any depth. (see diagram).
I looking for the best algorithm that would return an integer that represents the level of the deepest collection in the hierarchy. (So in my diagram that would be 4.).
I've tried the following function recursively but it is always out by one.
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;
}
Many thanks
答案1
得分: 1
我不太确定您所拥有的数据结构，所以我使用了一个没有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));
我希望这能帮助您理解代码。
英文:
I'm not 100% sure of the data structure you've got so I mocked a simpler one with out any children() methods, hope it still makes sense though.
I think that part of what makes your solution a bit trickier is that you start with the children rather than the node, afterall if you have one node with no children it should still have a depth of one (if I've understood things correctly). By passing the depth into the getLevelFunc at each stage I think it probably makes it easier to see what should be going on in the code.
<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
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));
<!-- end snippet -->
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论