在树中深入查找对象，然后 return 对象及其通过树的路径

Question

我已经编写了一个递归函数来查找给定对象和该树中的路径，但是当我将目标 id（在此处：if(tree.targetModuleId === 7)）更改为 10 时我收到错误：

"message": "Uncaught TypeError: Cannot read properties of undefined (reading 'unshift')"

我应该得到路径：[1,2,5,6,10]。

最后我需要一个选项，无论我想得到一条路线的哪个点，我都需要得到路线是什么的答案，如果没有则得到 []

我很想获得有关该主题的帮助，附上我编写的代码。

let nodes = [
  { sourceModuleId: 1, targetModuleId: 2},
  { sourceModuleId: 1, targetModuleId: 8},
  { sourceModuleId: 2, targetModuleId: 3},
  { sourceModuleId: 2, targetModuleId: 5},
  { sourceModuleId: 8, targetModuleId: 9},
  { sourceModuleId: 3, targetModuleId: 7},
  { sourceModuleId: 5, targetModuleId: 6},
  { sourceModuleId: 6, targetModuleId: 10},

];

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.targetModuleId, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];

    if (item.sourceModuleId !==1) {
      let parentItem = arrMap.get(item.sourceModuleId);
      
      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

function findInTree(tree) {
  
  if (tree.targetModuleId === 7) {
    let path = [tree.sourceModuleId,tree.targetModuleId];
    return {result: tree, path};
  } 
  if(tree.children){
    for(let i=0; i< tree.children.length;i++){
      let tmp = findInTree(tree.children);
      if (tmp) {
        tmp.path.unshift(tree.sourceModuleId);
        return tmp;
      }
    }
  }  
  else {
     for (let i = 0;i< tree.length; i++) {      
      let tmp = findInTree(tree[i]);
      if (tmp) {
        return tmp;
      }
    }
    return [];
  }
}
let tree = toTree(nodes);
let paths = findInTree(tree);
console.log(paths);

Answer 1

findInTree 中的一些问题：

return [] 不正确：这是一个真值，因此调用者的 if (tmp) 将为真，但它不应该为真。你的函数returns的数据类型应该是一致的。它似乎应该是一个具有 result 和 path 属性的对象，但是在你的代码中有一个 return [] 是不一致的。使 return null，以指示没有这样的对象，并且根据调用者的预期行为，此值将是假的。将此 return null 移出 else 块，这样当 if 块不执行 return.
时它也适用
在 if (tree.children) 块中，没有必要遍历这些子项，因为这将在递归调用中发生。请注意您从未在该循环中使用 i，因此重复该主体是浪费时间。只需删除循环。

function findInTree(tree) {
  if (tree.targetModuleId === 7) {
    let path = [tree.sourceModuleId, tree.targetModuleId];
    return {result: tree, path};
  } 
  if (tree.children) { 
      // No need to loop. It will happen in the recursive call
      let tmp = findInTree(tree.children);
      if (tmp) {
        tmp.path.unshift(tree.sourceModuleId);
        return tmp;
      }
  }  
  else {
    for (let i = 0;i< tree.length; i++) {      
      let tmp = findInTree(tree[i]);
      if (tmp) {
        return tmp;
      }
    }
  }
  return null; // data type consistency
}

在树中深入查找对象，然后 return 对象及其通过树的路径

Deep find object in tree, then return object and the path to it through the tree

javascript

algorithm

recursion

typescript

reactjs