JavaScript - 递归查找父节点

Question

我有一个用 JavaScript 编写的应用程序。在这个应用程序中，我有一棵 JavaScript 对象树。示例树和下面的代码可以在这个 JSFiddle 中看到.

我正在尝试编写一个函数，该函数将返回作为祖先的 ID 列表。具有特定 ID 的元素的祖先。目前，我有以下内容:

function getAncestors(childId, branch) {
  var ancestors = [];
  for (var i = 0; i < branch.length; i++) {
    for (var j = 0; j < branch[i].children.length; j++) {
      if (branch[i].children[j].id === childId) {
        ancestors.push(branch[i].id);
        return ancestors;
      } else {
        var _ancestors = getAncestors(childId, branch[i].children);
        for (var k = 0; k < _ancestors.length; k++) {
          if (ancestors.indexOf(_ancestors[k]) === -1) {
            ancestors.push(_ancestors[k]);
          }
        }
      }
    }
  }
  return ancestors;
}

它总是返回第一个父级。但是，它不会返回所有祖先。例如，在 JSFiddle ，我正在尝试获取一个包含以下内容的数组:[201, 2]，按该顺序排列。我不确定我做错了什么。我一直盯着这个，它看起来是正确的。但是，很明显，它不起作用。

Answer 1

这是工作代码(使用迭代):

function getAncestors(childId, newbranch) {
    for (var i = 0; i < newbranch.length; i++) { // Search all branches
        var branch = newbranch[i];

        if (branch.id === childId) {
            return [];
        } else {
            if (branch.children && branch.children.length) {
                var x;

                if ((x = getAncestors(childId, branch.children)) !== false) {
                    x.push(branch.id)
                    return x;
                }
            }
        }
    }

    return false;
}

结果:

[201,2]

编辑(更短)

function getAncestors(childId, branch) {
    var i, ancestors;

    for (i = 0; !ancestors && branch && i < branch.length; i++) {
        if (branch[i].id === childId) return [];
        ancestors = getAncestors(childId, branch[i].children);
        if (ancestors) ancestors.push(branch[i].id);
    }
    return ancestors;
}