什么是深度优先遍历

深度优先遍历就是当我们搜索一个树的分支时，遇到一个节点，我们会优先遍历它的子节点，直到最后根节点位置，最后再遍历兄弟节点，从兄弟节点寻找它的子节点，知道搜索到最后结果，然后结束。

  1. const root = {
  2.   name: '1',
  3.   children: [
  4.     {
  5.       name: '2-1',
  6.       children: [
  7.         {
  8.           name: '3-1',
  9.           children: [
  10.             {
  11.               name: '4-2',
  12.               children: null
  13.             },
  14.             {
  15.               name: '4-1',
  16.               children: null
  17.             }
  18.           ]
  19.         },
  20.         {
  21.           name: '3-2',
  22.           children: null
  23.         }
  24.       ]
  25.     },
  26.     {
  27.       name: '2-2',
  28.       children: null
  29.     }
  30.   ]
  31. }
  33. // 深度优先遍历
  34. const deepDFS = (root, nodeList = []) => {
  35.   if(root) {
  36.     nodeList.push(root.name);
  37.     root.children && root.children.forEach(v => deepDFS(v, nodeList));
  38.   }
  39.   return nodeList;
  40. }
  41. const result = deepDFS(root, []);
  43. /**
  44. [
  45.   "1",
  46.   "2-1",
  47.   "3-1",
  48.   "4-2",
  49.   "4-1",
  50.   "3-2",
  51.   "2-2"
  52. ]
  53. **/

什么是广度优先遍历

搜索树分支时，从根节点开始，当访问子节点时，先遍历找到兄弟节点，再寻找对应自己的子节点。
image.png

const deepBFS = (root, nodeList = []) => {
  const queue = [root];
  while(queue.length > 0) {
    const p = queue.shift();
    nodeList.push(p.name);
    p.children && p.children.forEach(v => queue.push(v));
  }
  return nodeList;
}

/*
[
  "1",
  "2-1",
  "2-2",
  "3-1",
  "3-2",
  "4-2",
  "4-1"
]
*/

广度优先遍历的主要思想是将一个树放到一个队列中，我们循环这个队列，判断该队列的长度是否大于0，不断循环队列，shift出队列操作，然后判断节点children，循环children，然后将子节点添加到队列中，一旦队列长度为0，那么就终止循环了。

总结

  1. 理解深度优先遍历与广度优先遍历是什么
  2. 用具体代码实现深度优先遍历与广度优先遍历
  3. 深度优先更耗时 ```javascript const deepDFS = (root, nodeList = []) => { if(root) { nodeList.push(root.name); root.children && root.children.forEach(v => deepDFS(v, nodeList)); } return list; }

const deepBFS = (root, nodeList = []) => { let queue = [root]; while(queue.length > 0) { const curr = queue.shift(); nodeList.push(curr.name); curr.children && curr.children.forEach(v => queue.push(v)); } return nodeList; } ```