1

我正在努力将下面的 JS 递归函数转换为一个蹦床函数，以避免使用深节点最大化调用堆栈。

它从传入的初始根节点返回一个包含所有子节点的数组。注意，list 是一个 Map，用于查找当前节点的子节点以进行下一次递归迭代。

const getRootSet = (nodeId, list) => {    
  let results = [];
  const node = list.get(nodeId);

  if (node && node.children.size > 0) {       
    results.push(node.nodeId);
    node.children.forEach((value, key) => {
        results = results.concat(getRootSet(list.get(key).nodeId, list) );
    });
  }

  if(node && node.children.size === 0)
  {
    //add last child node
    results.push(node.nodeId);
  }
  return results;
}

如何设置蹦床结构以构建节点数组以在最后返回？

Sample data:
child, parent,
111111, 222222,
000000, 111111,
060270, 964240,
041342, 964240,
024367, 964240,
052643, 964240,
083020, 060270,
024367, 961758,
024367, 964264,
060270, 024367,
060270, 964240,
123456, 789100,
345678, 789100,
4

1 回答 1

0

我们知道递归使用内存堆栈来推送和记住下一个递归函数调用，所以我们需要一些东西来记住我们的下一个函数调用。在这里，我使用nodes数组来推送下一个执行周期的子节点 ID。在每个节点 id 上，我们首先检查它是否存在于list地图中。如果是，则将其推入results并迭代其子代，并将子代 ID 推入nodes下一个周期。请注意，我正在检查子 ID 是否已被处理，以避免循环无限循环。对于我正在使用的当前节点index，断点是nodes. 这是我的解决方案：

const getRootSet = (rootNodeId, list) => {    
   let results = [];
   let nodes = [rootNodeId];
   let index = 0;
   while(index < nodes.length) {
     const node = list.get(nodes[index]);
     if(node) {
       results.push(node.nodeId);
       if (node.children.size > 0) {
         node.children.forEach((val, childId) => {
            if(!nodes.includes(childId)) {
              nodes.push(childId);
            }
         });
       }
     }
     index++;
   }
      
  return results;
};

console.log(getRootSet('root', list));

这是 js 中的示例代码：https ://ideone.com/Avnq9h

于 2021-03-03T03:42:39.177 回答