Нахождение объектов в дереве объектов между корнем и любым объектом

Question

У меня есть типичная древовидная структура данных, которая выглядит следующим образом:

[
  {
    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 возвращаются не только объекты правильного пути, но и многие другие объекты дерева.

Answer 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);    
}