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

从上到下打印二叉树 III

题目

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

示例

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

返回其层次遍历结果：

解题思路

算法流程：

1. BFS 循环： 循环打印奇 / 偶数层，当 queue 为空时跳出；
2. 打印奇数层： 从左向右 打印，先左后右 加入下层节点；
3. 若 queue 为空，说明向下无偶数层，则跳出；
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 [];}// 记录结果let res = [];// 记录每层节点数let tmp = [];// 辅助队列let queue = [root];// 单双层标记let flag =true;// 当辅助队列不为空时遍历while(queue.length !==0) {
    //清空临时数组列表tmp = []// 记录当层节点数量var length =queue.length;// 遍历当层节点while(length--){
    let first = queue.shift();tmp.push(first.val);if(first.left){
    queue.push(first.left)}if(first.right){
    queue.push(first.right)}}// 当层数为单层时压入结果中,否则翻转后压入结果中if(flag){
    res.push(tmp)}else{
    res.push(tmp.reverse())}// 层数单双切换flag=!flag;}// 返回结果return res;
};