每日算法

二叉树的层序遍历

现在我们要做的是对这个二叉树进行层序遍历。层序遍历的概念很好理解：按照层次的顺序，从上到下，从左到右地遍历一个二叉树

• 模拟一个二叉树

  const root = {
              val: "A",
              left: {
                  val: "B",
                  left: {
                      val: "D"
                  },
                  right: {
                      val: "E"
                  }
              },
              right: {
                  val: "C",
                  right: {
                      val: "F"
                  }
              }
          };

• 开始遍历(每层从左到右一次访问)

  function BFS(root) {
          // 数组模拟队列
          const queue = []
          // 先把root入队
          queue.push(root)
          while(queue.length) {
              //取出队列顶元素
              const top = queue[0]
              //访问值
              console.log(top.val);
              if(top.left) {
                  queue.push(top.left)
              }
              if(top.right) {
                  queue.push(top.right)
              }
              queue.shift()
          }
      }   
      BFS(root)

  ​