javascript - 在嵌套对象数组中查找父对象。如何？

Question

我有一个如下所示的数据结构:

var someDataStructure = [
  {
    opts: {_id:1}
  },
  {
    opts: {_id: 2},
    children: [
      {
        opts: {_id: 3},
        children: [
          {
            opts: {_id: 4}
          }
        ]
      }
    ]
  },
  {
    opts: {_id: 5}
  },
  {
    opts: {_id: 6},
    children: [
      {
        opts: {_id: 7},
        children: [
          {
            opts: {_id: 8}
          }
        ]
      }
    ]
  }  
];

这是一个对象数组，所有对象都具有一个opts 属性和一个可选的children 属性。如果它存在，children 属性将是同类对象的数组。

给定任何 opts._id，我需要找到所有父对象的 _id。我在这里给出的 _id 只是为了方便而顺序排列的。 您可能不会假设它们是连续整数

这个项目同时使用了 jquery 和 lodash，所以这两个库都可以使用。

示例所需的输出:

• 给定4，返回[2, 3]。
• 给定3，返回[2]。
• 给定 8，返回 [6, 7]。
• 给定7，返回[6]。

我可以毫无问题地递归并找到给定的 _id。但是，我觉得很愚蠢，坚持维护 parent 的数组。

Answer 1

如果找到，返回找到状态和 parent 的解决方案。

function getParentsHelper(tree, id, parents) {
    if (tree.opts._id == id) {
        return {
            found: true,
            parents: parents
        };
    }
    var result = {
        found: false,
    }
    if (tree.children) {
        $.each(tree.children, function(index, subtree) {
            var maybeParents = $.merge([], parents);
            if (tree.opts._id != undefined) {
                maybeParents.push(tree.opts._id);
            }
            var maybeResult = getParentsHelper(subtree, id, maybeParents);
            if (maybeResult.found) {
                result = maybeResult;
                return false;
            }
        });
    }
    return result;
}

function getParents(data, id) {
    var tree = {
        opts: { },
        children: data
    }
    return getParentsHelper(tree, id, []);
}

使用示例:

console.log(getParents(someDataStructure, 4).parents);
console.log(getParents(someDataStructure, 3).parents);
console.log(getParents(someDataStructure, 8).parents);
console.log(getParents(someDataStructure, 7).parents);