广度优先遍历 BFS(Breath First Search)

[Betty985]

思想

• BFS的思想是从左到右，对树每一层中所有节点依次遍历，当一层的节点遍历完全后，对下一层开始遍历，而下一层节点是上一层的子节点，符合队列先进先出的特点

• 特性：保留全部节点，占用空间大，无回溯操作，运行速度快。

  递归

  function wideTraversal(node) {
  let nodes=[]
  let i=0
  if(node !=null){
      nodes.push(node)
      wideTraversal(node.nextElementSlibing)
      node=nodes[i++]
      wideTraversal(node.firstElementChild)
  }
  return nodes
  }

  非递归

  function wideTraversal(node){
  let nodes=[]
  let i=0
  while(node!=null){
      nodes.push(node)
      node=nodes[i++]
      let childrens=node.chilren
      for(let j=0;j<childrens.length;j++){
          nodes.push(childrens[j])
      }
  }
  return nodes
  }

  多叉树的层序遍历

  将节点按层入队，队列中只存储当前层和下一层的节点。队列长度不为0 时，进入循环并记录下此时队列的长度（即当前层的节点个数）。让节点依次出队，将节点值放入当前层的数组，并将节点的children入队。当前节点全部出队后，将当前层的节点放入结果数组。

  
  var levelOrder = function(root) {
  if (!root) {
      return [];
  }
  
  const ans = [];
  const queue = [root];
  
  while (queue.length) {
      const size= queue.length;
      const level = [];
      for (let i = 0; i < size; ++i) {
          const cur = queue.shift();
          level.push(cur.val);
          for (const child of cur.children) {
              queue.push(child);
          }
      }
      ans.push(level);
  }
  
  return ans;
  };