获取父 node.name 递归无法正常工作

Question

我有一棵无限大的树：

const Data = [
  {
    id: '1',
    name: 'hello',
    children: [
      {
        id: '2',
        name: 'world',
        children: [
          {
            id: '3',
            name: 'world',
            children: [],
          },
          {
            id: '4',
            name: 'world',
            children: [],
          },
        ],
      },
      {
        id: '5',
        name: 'world',
        children: [],
      },
    ],
  },
];

我想做的是获取通往“世界”的路径的 ID 和名称，并将其推入数组。

例如：第一个路径是：

  [
    { id: '1', name: 'hello' },
    { id: '2', name: 'world' },
  ]

第二个：

  [
    { id: '1', name: 'hello' },
    { id: '2', name: 'world' },
    { id: '3', name: 'world' },
  ]

然后将这些数组推入另一个数组。

所以我的结果应该是这样的：

const result = [
  [
    { id: '1', name: 'hello' },
    { id: '2', name: 'world' },
  ],
  [
    { id: '1', name: 'hello' },
    { id: '2', name: 'world' },
    { id: '3', name: 'world' },
  ],
  [
    { id: '1', name: 'hello' },
    { id: '2', name: 'world' },
    { id: '4', name: 'world' },
  ],
  [
    { id: '1', name: 'hello' },
    { id: '5', name: 'world' },
  ],
];

我有一个递归函数：

const findPath = (input="world", data, visitedStack, dataStack) => {
  return data.map((node) => {
    visitedStack.push({ id: node.id, name: node.name });
    if (node.name.toLowerCase().includes(input.toLowerCase())) {
      dataStack.push([...visitedStack]);
    }
    return findPath(
      input,
      node.children,
      visitedStack,
      dataStack
    );
  });
};

但是这是在它访问过的所有路径上添加，所以最后一个被压入 dataStack 的数组看起来像这样：

  [
    { id: '1', name: 'hello' },
    { id: '2', name: 'world' },
    { id: '3', name: 'world' },
    { id: '4', name: 'world' },
    { id: '5', name: 'world' },
  ]

不知道如何解决这个问题。或者这是一种不正确的方法？

Answer 1

问题是您的 visitedStack 不断增长，因为您最终将所有节点推向它。请注意，函数的所有递归执行都使用相同的 visitedStack 。所以推[...visitedStack]不会推路径，而是之前访问过的所有节点，一段时间后不再代表路径。

如果我们坚持使用你的函数，那么只要确保你不会永久推进 visited，而是创建一个带有额外节点的堆栈副本，它将保留在更深层次的递归中，但是不会污染整个执行的其余部分。这样，额外的节点就不会存在于其他同级路径中：

const findPath = (input="world", data, visitedStack, dataStack) => {
  return data.map((node) => {   
    let newStack = visitedStack.concat({ id: node.id, name: node.name });
    if (node.name.toLowerCase().includes(input.toLowerCase())) {
      dataStack.push(newStack);
    }
    return findPath(
      input,
      node.children,
      newStack,
      dataStack
    );
  });
};

呼叫为：

let result = [];
findPath("world", data, [], result);
console.log(result);

备选

不过，我还要解决以下问题：

有点奇怪findPath没有return结果，但是调用者需要提供数组应在其中收集结果路径。所以我会建议一个函数 returns 新数组，不需要调用者将该数组作为参数传递。
当参数后面的其他参数没有默认值时，为参数设置默认值是没有用的。因为，这意味着您无论如何都必须为其他参数提供值，包括可能具有默认值的参数。
return编辑的路径仍然包含对相同对象的多个引用。您确实将对象复制到新对象中，但由于该新对象位于 visitedStack 中，它将在可能被推送多次以获得更深的路径时被重用。所以我建议在最后一刻制作对象副本——当路径推到结果数组时。
与其反复将输入转换为小写，不如只执行一次。

你可以这样写：

function findPath(data, input="world") {
    const result = [];
    input = input.toLowerCase();
    
    function recur(data, visitedStack) {
        for (const node of data) {
            const newStack = visitedStack.concat(node);
            if (node.name.toLowerCase().includes(input)) {
                result.push(newStack.map(o => ({id: o.id, name:o.name})));
            }
            recur(node.children, newStack);
        }
    }

    recur(data, []);
    return result;
}

const data = [{id: '1',name: 'hello',children: [{id: '2',name: 'world',children: [{id: '3',name: 'world',children: [],},{id: '4',name: 'world',children: [],},],},{id: '5',name: 'world',children: [],},],},];

const result = findPath(data);
console.log(result);

获取父 node.name 递归无法正常工作

Getting parent node.name recursion is not working properly

javascript

recursion

tree

treeview

备选