二叉树-层序遍历

• 按照一层层从上到下，从左到右的顺序进行遍历，本质是BFS

• 递归方法

  • 利用前序遍历+分层存储的方式，达到层序遍历的效果

  function levelOrderTraversal(root) {
      const res = [];
      let levelOrderTraverseNode(node, level) {
          if (!node) return;
          res[level] = res[level] || [];
          res[level].push(node.key);
          levelOrderTraverseNode(node.left, level + 1);
          levelOrderTraverseNode(node.right, level + 1);
      }
      levelOrderTraverseNode(root, 0);
  
      return res;
  }
  

• 迭代方法，也叫队列方法【常用】

  function levelOrderTraversal(root) {
      if (!root) return [];
      const res = [];
      const queue = [root];
      let level = 0;
      while(queue.length > 0) {
          res[level] = [];
          const len = queue.length;
          for (let i = 0; i < len; i++) {
              const node = queue.shift();
              res[level].push(node.key);
              if (node.left) queue.push(node.left);
              if (node.right) queue.push(node.right);
          }
          level++:
      }
      return res;
  }