从上到下打印二叉树

• 算法与数据结构
• 2020-09-22 09:25:58

问题：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。（来自剑指offer 32-1）

例如：给定二叉树: [3,9,20,null,null,15,7]

  3

   / \

  9  20

    /  \

   15   7

返回：[3,9,20,15,7]

解法：广度优先遍历

/**
 * @desc 从上到下打印二叉树
 * @param {TreeNode} root
 * @return {number[]}
 */
let levelOrder = function(root) {
  if (!root) return [];
  let res = [], queue = [root]; // 利用队列来广度优先遍历
  while (queue.length) { // 如果队列为空则返回结果
    let temp = queue.shift(); // 取出队头
    res.push(temp.val); // 将值追加到结果中
    temp.left && queue.push(temp.left); // 如果左子树不为空，则在队列后面追加
    temp.right && queue.push(temp.right); // 如果右子树不为空，则在队列后面追加
  }
  return res;
};