栈与深度优先搜索(DFS)

与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径。
与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。条路径并不总是最短的路径。

/*
 * Return true if there is a path from cur to target.
 */
function DFS(root, target) {
  if (!root) return false;
  let set = new Set();

  function loop(node, target) {
    if (node) {
      if (node.id === target) return true;
      if (!set.has(node)) {
        set.add(node);
        if (node.children) {
          for (let i = 0, len = node.children.length; i < len; i++) {
            const cur = node.children[i];
            if (loop(cur, target)) return true;
          }
        }
      }
    }
  }

  if (Array.isArray(root)) {
    for (let i = 0, len = root.length; i < len; i++) {
      if (loop(root[i], target)) return true;
    }
  } else {
    if (loop(root, target)) return true;
  }
  return false;
}
const nodeE = { id: 'e' };
const nodeG = { id: 'g' };
const data = {
  id: 'a',
  children: [
    { id: 'b', children: [nodeE] },
    { id: 'c', children: [nodeE, { id: 'f', children: [nodeG] }] },
    { id: 'd', children: [nodeG] }
  ]
};
// debugger;
console.log(DFS(data, 'g')); // true