【leecode 剑指offer】从上到下打印二叉树

从上到下打印二叉树

题目

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

示例

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

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

思路

BFS

层序遍历需要使用一个队列来存储有用的节点。整体的思路如下：
子节点顺序：自左向右

1. 将 root 放入队首
2. 取出队首元素，将 val 放入返回的数组中
3. 检查队首元素的子节点，若不为空，则将子节点放入队列
4. 检查队列是否为空，为空，结束并返回数组；不为空，回到第二步

代码实现

/*** Definition for a binary tree node.* function TreeNode(val) {* this.val = val;* this.left = this.right = null;* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var levelOrder = function(root) {
    // 当二叉树为空时返回空数组if(!root){
    return [];}// 存储数据var res = [];// 辅助队列，用于记录遍历的层数 BFSvar queue = [root];// 当辅助队列不为空时while(queue.length){
    // 移除队首元素let first = queue.shift();//返回值为移除的元素// 将元素的值插入结果队列中res.push(first.val);// 左元素不为空，加入队列if(first.left){
    queue.push(first.left);}// 右元素不为空，加入队列if(first.right){
    queue.push(first.right);}}// 返回结果队列return res;
};

总结

	这个题目主要考察的是二叉树的按层遍历，按层遍历的关键在于记录遍历的层数，而我使用的是一个辅助队列去帮助记录，对二叉树进行广度遍历。