javascript - 如何找到给定ID的路径？

Question

我有一棵树：

type Tree = {
  id: string;
  pathToNode?: string[];
  children: Tree[];
};

export const treeData: Tree = {
  id: '1',
  children: [
    {
      id: '2',
      children: [
        { id: '3', children: [] },
        { id: '4', children: [] },
      ],
    },
    { id: '5', children: [] },
  ],
};

我希望找到 id 的路径并返回该路径（或者换句话说，该节点的父节点）。

这就是我所拥有的（但它不起作用）：

const findPath = (tree: Tree, id: string, pathStack: string[]) => {
  if (tree.id === id) {
    tree.pathToNode = pathStack;
    return { id: tree.id, path: tree.pathToNode };
  }
  pathStack.push(tree.id);

  if (tree.children.length) {
    tree.children.map((node) => findPath(node, id, pathStack));
  }

  return { id: tree.id, path: pathStack };
};

如果我调用 findPath 并传入 id:'2'，我应该得到：

const pathStack:string[] = [];

const result = findPath(treeData, '2', pathStack);
// result should equal: {id: '2', pathToNode: ['1']}

如果我调用 findPath 并传入 id:'4'，我应该得到：

const pathStack:string[] = [];

const result = findPath(treeData, '4', pathStack);
// result should equal: {id: '4', pathToNode: ['1', '2']}

如果我调用 findPath 并传入 id:'5'，我应该得到：

const pathStack:string[] = [];

const result = findPath(treeData, '5', pathStack);
// result should equal: {id: '5', pathToNode: ['1']}

如果我传入 '1' 的根 id，响应将是 {'1', pathToNode: []}

标签： javascripttypescriptrecursiontreetreeview

Answer 1

您需要为孩子们​​早日返回并尊重返回值。

const
    treeData = { id: '1', children: [{ id: '2', children: [{ id: '3', children: [] }, { id: '4', children: [] }] }, { id: '5', children: [] }] },
    findPath = (tree, id, pathStack = []) => {
        if (tree.id === id) return { id: tree.id, path: pathStack };

        pathStack.push(tree.id);

        for (const node of tree.children) {
            const result = findPath(node, id, [...pathStack]);
            if (result) return result;
        }
    };
    

console.log(findPath(treeData, '4'));
console.log(findPath(treeData, '5'));