javascript - 在对象树中查找从根到任意对象之间的对象

我有一个典型的树形数据结构，看起来像这样：

[
  {
    data: object,
    subs:
      [ ...other objects... ]
  },
  ...other objects...
]

它可以有任何形状和任意数量的节点。

我写了一个方法，应该递归地查找并返回从根 r 到给定对象 o 的路径（中间对象的数组）。（是否包含 r 和 o 我不在乎）

public getPath(tree: Array<object>, o: object): Array<object> {

  let path: Array<object> = [];

  function f(subtree: Array<object>): void {
    for (let node of subtree) {

      path.push(node['data']);
      if (node['data'] == o) return;
      else if (node['subs'].length > 0) f(node['subs']);
      else path = [];

    }
  }

  f(tree);
  return path;

}

基本上我的想法是

总是将从 r 到 o 遍历过程中访问的每个对象添加到数组中，
如果遍历了一条不是从r到o的路径，则清空数组，
并在到达应结束遍历的 o 时返回。

结果：

它将 r 用作 o，返回 [r]。
它也适用于 r 的第一个子节点作为 o，返回 [r，r 的第一个子节点]。
但是，如果选择任何其他对象作为o，不仅返回正确路径的对象，还会返回树中许多其他对象。

答案＃1

你的代码的缺陷在于你使用了一个全局的（无论如何在 f 的作用域之外）path 数组。问题在于，如果节点不匹配，你会清空整个数组，而实际上你只应该删除当前部分。有两种方法可以实现你想要的效果：第一种是让 f 接受一个数组 path，复制它并递归传递直到找到对象；另一种方法，也是最好的方法，是利用调用栈（由递归创建的）：

public getPath(tree: Array<object>, o: object): Array<object> {

    function f(subtree: Array<object>) {                              // I don't know typescript, so specify the return type as (Array<object> or null)
        for (let node of subtree) {
            if (node.data == o) {                                     // if this is the node we're looking for
                return [node];                                        // return an array (which will be our path), here you can either return [] to exclude the matched node (o) or [node] to include it
            } else if(node.subs.length) {                             // not the node we are looking for, but it has children, so let check'em out 
                let result = f(node.subs);                            // result will either be an array (if we recursively found something), or null otherwise
                if(result) {                                          // if we found something, then result will be the path from the current node to the object o (the current node not included)
                    result.unshift(node);                             // we include the current node by pushing it into the result array (pushing it to the first position)
                    return result;                                    // return result (an array) to signal successfulness
                }
            }
        }
        return null;                                                  // the object o not found in this subtree, return null to signal unsuccessfullness. Kind of redundant, because undefined is returned by default, so feel free to remove it
    }

    return f(tree);    
}